问一道递归的题！告诉我思路就好！
其实是一道题的两个问题，写一个递归函数1.input一个“表达式”，计算出他的结果。
2.input一个字符串，判断他是不是“表达式”，如果是则返回0，如果不是则返回第一个错误/多余的字符的位置。
表达式的定义是：<小括号（> <数字> <加减乘（+-*）><数字><小括号）>
例子：（1+（2*2）是表达式，（（（2*1）+1）-1）也是。
我想了两个小时也没什么思路555
告诉我思路就好，感激不尽！！！ 1. 你没有说要使用的编程语言，而且把问题发在了 新手乐园 版块
所以我不知道你要求用哪个语言写，看你的问题中出现了 input 这个单词，初步判断是用python
2. python中的这个input函数每一次都会得到一行输入，但是我需要一次得到一个字符，而且有时候还需要把这个字符退回去，用input函数就需要自己写一个字符一个字符读取和退回字符的代码，C语言中有fgetc和ungetc函数，这两个函数就是我想要的，这里就直接调用C语言的这两个函数
3. 我干脆帮你把这两个要求合并一下吧，毕竟两个要求有太多相同的地方
合并成这样
输入一个字符串，如果是“表达式”，那就计算结果然后输出，如果不是“表达式”，那就报告错误
#!/usr/bin/env python
#coding=utf-8
from ctypes import cdll
from ctypes.util import find_library
from ctypes import c_void_p, c_int, byref
import sys
libc = cdll.LoadLibrary(find_library('c'))
stdin = c_void_p.in_dll(libc, 'stdin')
def fgetc(stream):
return libc.fgetc(stream)
def ungetc(ch, stream):
return libc.ungetc(ch, stream)
# token
# [, lchild, rchild]
last_token = None
file_rows = 1
file_cols = 1
ERROR = 256
NUM = 257
EOF = -1
def error(value):
return [, value, value], None, None]
def isdigit(ch):
return ch >= ord('0') and ch <= ord('9')
def get_token():
global last_token
if last_token:
result = last_token
last_token = None
return result
global file_cols, file_rows
last_position =
ch = fgetc(stdin)
file_cols += 1
if ch in ]:
return get_token()
if isdigit(ch):
ungetc(ch, stdin)
file_cols -= 1
num = c_int()
libc.fscanf(stdin, b'%d', byref(num))
file_cols += len(str(num.value))
return [, None, None]
if ch == ord('\n'):
file_rows += 1
file_cols = 1
return [, None, None]
def unget_token(token):
global last_token
last_token = token
def factor():
token = get_token()
if token == NUM: return token
if token == ord('-'):
token = factor()
if token == ERROR: return token
return token
if token != ord('('): return error(token)
token = expression()
if token == ERROR: return token
temp = token
token = get_token()
if token != ord(')'): return error(token)
return temp
def term():
token = factor()
if token == ERROR: return token
a = token
token = get_token()
if token != ord('*') and token != ord('/'):
unget_token(token)
return a
op = token
token = term()
if token == ERROR: return token
b = token
op = a
op = b
return op
def expression():
token = term()
if token == ERROR: return token
a = token
token = get_token()
if token != ord('+') and token != ord('-'):
unget_token(token)
return a
op = token
token = expression()
if token == ERROR: return token
b = token
op = a
op = b
return op
def do_error(info):
print('错误的表达式!', file = sys.stderr)
print(f'(\'{chr(info)}\',{info,info})', file = sys.stderr)
while True:
token = get_token()
if token == ord('\n'): break
def val(tree):
if tree == NUM: return tree
if tree == ord('+'): return val(tree) + val(tree)
if tree == ord('*'): return val(tree) * val(tree)
if tree == ord('/'): return val(tree) / val(tree)
if tree == ord('-'):
return -val(tree) if tree == None else val(tree) - val(tree)
raise "未知的运算符!"
def line():
token = get_token()
if token == ord('\n'): return
unget_token(token)
token = expression()
if token == ERROR:
do_error(token)
return
result = token
token = get_token()
if token == ord('\n'):
#print(result)
print('>>> ' + str(val(result)))
return
do_error(token)
def lines():
token = get_token()
unget_token(token)
if token == EOF:
return
line()
lines()
return
def start():
lines()
token = get_token()
if token == EOF: return True
return False
print(start())
参考: https://fishc.com.cn/thread-213764-1-1.html
这东西不是用栈吗 用栈机制来处理括号 小甲鱼有专门讲这个的视频 排程場演算法（或调度场算法）和逆波兰表示法
https://fishc.com.cn/thread-212875-1-1.html 中缀改成后缀（逆波兰）表达式，如果表达式合法再计算
用栈实现
具体见小甲鱼的数据结构和算法篇——栈和队列 改一下
print(f'(\'{chr(info)}\',{info,info})', file = sys.stderr)
print(f'(\'{chr(info)}\', {info,info})', file = sys.stderr) 感谢楼上的各位老哥，我这就去看视频。最佳答案给帮忙写了代码的老哥啦（虽然其实我用的是c++哈哈哈，不过还是很感谢您！） {:5_109:}
页:
[1]