[已解决]问一道递归的题！告诉我思路就好！

猫皇

其实是一道题的两个问题，写一个递归函数
1.input一个“表达式”，计算出他的结果。
2.input一个字符串，判断他是不是“表达式”，如果是则返回0，如果不是则返回第一个错误/多余的字符的位置。
表达式的定义是：<小括号（> <数字> <加减乘（+-*）><数字><小括号）>
例子：（1+（2*2）是表达式，（（（2*1）+1）-1）也是。

我想了两个小时也没什么思路555
告诉我思路就好，感激不尽！！！

最佳答案

月排行榜 / 总排行榜

人造人

2022-6-26 11:46:47

1. 你没有说要使用的编程语言，而且把问题发在了 新手乐园 版块
所以我不知道你要求用哪个语言写，看你的问题中出现了 input 这个单词，初步判断是用python
2. python中的这个input函数每一次都会得到一行输入，但是我需要一次得到一个字符，而且有时候还需要把这个字符退回去，用input函数就需要自己写一个字符一个字符读取和退回字符的代码，C语言中有fgetc和ungetc函数，这两个函数就是我想要的，这里就直接调用C语言的这两个函数
3. 我干脆帮你把这两个要求合并一下吧，毕竟两个要求有太多相同的地方
合并成这样
输入一个字符串，如果是“表达式”，那就计算结果然后输出，如果不是“表达式”，那就报告错误

1. #!/usr/bin/env python
   
2. #coding=utf-8
   
3. 
   
4. from ctypes import cdll
   
5. from ctypes.util import find_library
   
6. from ctypes import c_void_p, c_int, byref
   
7. import sys
   
8. 
   
9. libc = cdll.LoadLibrary(find_library('c'))
   
10. stdin = c_void_p.in_dll(libc, 'stdin')
    
11. 
    
12. def fgetc(stream):
    
13.     return libc.fgetc(stream)
    
14. 
    
15. def ungetc(ch, stream):
    
16.     return libc.ungetc(ch, stream)
    
17. 
    
18. # token
    
19. # [[symbol, value, rows, cols], lchild, rchild]
    
20. last_token = None
    
21. file_rows = 1
    
22. file_cols = 1
    
23. 
    
24. ERROR = 256
    
25. NUM = 257
    
26. EOF = -1
    
27. 
    
28. def error(value):
    
29.     return [[ERROR, value[1], value[2], value[3]], None, None]
    
30. 
    
31. def isdigit(ch):
    
32.     return ch >= ord('0') and ch <= ord('9')
    
33. 
    
34. def get_token():
    
35.     global last_token
    
36.     if last_token:
    
37.         result = last_token
    
38.         last_token = None
    
39.         return result
    
40.     global file_cols, file_rows
    
41.     last_position = [file_rows, file_cols]
    
42.     ch = fgetc(stdin)
    
43.     file_cols += 1
    
44.     if ch in [ord(i) for i in [' ', '\t', '\v', '\f']]:
    
45.         return get_token()
    
46.     if isdigit(ch):
    
47.         ungetc(ch, stdin)
    
48.         file_cols -= 1
    
49.         num = c_int()
    
50.         libc.fscanf(stdin, b'%d', byref(num))
    
51.         file_cols += len(str(num.value))
    
52.         return [[NUM, num.value, *last_position], None, None]
    
53.     if ch == ord('\n'):
    
54.         file_rows += 1
    
55.         file_cols = 1
    
56.     return [[ch, ch, *last_position], None, None]
    
57. 
    
58. def unget_token(token):
    
59.     global last_token
    
60.     last_token = token
    
61. 
    
62. def factor():
    
63.     token = get_token()
    
64.     if token[0][0] == NUM: return token
    
65.     if token[0][0] == ord('-'):
    
66.         token[1] = factor()
    
67.         if token[1][0][0] == ERROR: return token[1]
    
68.         return token
    
69.     if token[0][0] != ord('('): return error(token[0])
    
70.     token = expression()
    
71.     if token[0][0] == ERROR: return token
    
72.     temp = token
    
73.     token = get_token()
    
74.     if token[0][0] != ord(')'): return error(token[0])
    
75.     return temp
    
76. 
    
77. def term():
    
78.     token = factor()
    
79.     if token[0][0] == ERROR: return token
    
80.     a = token
    
81.     token = get_token()
    
82.     if token[0][0] != ord('*') and token[0][0] != ord('/'):
    
83.         unget_token(token)
    
84.         return a
    
85.     op = token
    
86.     token = term()
    
87.     if token[0][0] == ERROR: return token
    
88.     b = token
    
89.     op[1] = a
    
90.     op[2] = b
    
91.     return op
    
92. 
    
93. def expression():
    
94.     token = term()
    
95.     if token[0][0] == ERROR: return token
    
96.     a = token
    
97.     token = get_token()
    
98.     if token[0][0] != ord('+') and token[0][0] != ord('-'):
    
99.         unget_token(token)
    
100.         return a
     
101.     op = token
     
102.     token = expression()
     
103.     if token[0][0] == ERROR: return token
     
104.     b = token
     
105.     op[1] = a
     
106.     op[2] = b
     
107.     return op
     
108. 
     
109. def do_error(info):
     
110.     print('错误的表达式!', file = sys.stderr)
     
111.     print(f'(\'{chr(info[1])}\',{info[2],info[3]})', file = sys.stderr)
     
112.     while True:
     
113.         token = get_token()
     
114.         if token[0][0] == ord('\n'): break
     
115. 
     
116. def val(tree):
     
117.     if tree[0][0] == NUM: return tree[0][1]
     
118.     if tree[0][0] == ord('+'): return val(tree[1]) + val(tree[2])
     
119.     if tree[0][0] == ord('*'): return val(tree[1]) * val(tree[2])
     
120.     if tree[0][0] == ord('/'): return val(tree[1]) / val(tree[2])
     
121.     if tree[0][0] == ord('-'):
     
122.         return -val(tree[1]) if tree[2] == None else val(tree[1]) - val(tree[2])
     
123.     raise "未知的运算符!"
     
124. 
     
125. def line():
     
126.     token = get_token()
     
127.     if token[0][0] == ord('\n'): return
     
128.     unget_token(token)
     
129.     token = expression()
     
130.     if token[0][0] == ERROR:
     
131.         do_error(token[0])
     
132.         return
     
133.     result = token
     
134.     token = get_token()
     
135.     if token[0][0] == ord('\n'):
     
136.         #print(result)
     
137.         print('>>> ' + str(val(result)))
     
138.         return
     
139.     do_error(token[0])
     
140. 
     
141. def lines():
     
142.     token = get_token()
     
143.     unget_token(token)
     
144.     if token[0][0] == EOF:
     
145.         return
     
146.     line()
     
147.     lines()
     
148.     return
     
149. 
     
150. def start():
     
151.     lines()
     
152.     token = get_token()
     
153.     if token[0][0] == EOF: return True
     
154.     return False
     
155. 
     
156. print(start())
     

复制代码

参考: https://fishc.com.cn/thread-213764-1-1.html

跳转到最佳答案楼层

人造人

1. 你没有说要使用的编程语言，而且把问题发在了 新手乐园 版块
所以我不知道你要求用哪个语言写，看你的问题中出现了 input 这个单词，初步判断是用python
2. python中的这个input函数每一次都会得到一行输入，但是我需要一次得到一个字符，而且有时候还需要把这个字符退回去，用input函数就需要自己写一个字符一个字符读取和退回字符的代码，C语言中有fgetc和ungetc函数，这两个函数就是我想要的，这里就直接调用C语言的这两个函数
3. 我干脆帮你把这两个要求合并一下吧，毕竟两个要求有太多相同的地方
合并成这样
输入一个字符串，如果是“表达式”，那就计算结果然后输出，如果不是“表达式”，那就报告错误

1. #!/usr/bin/env python
   
2. #coding=utf-8
   
3. 
   
4. from ctypes import cdll
   
5. from ctypes.util import find_library
   
6. from ctypes import c_void_p, c_int, byref
   
7. import sys
   
8. 
   
9. libc = cdll.LoadLibrary(find_library('c'))
   
10. stdin = c_void_p.in_dll(libc, 'stdin')
    
11. 
    
12. def fgetc(stream):
    
13.     return libc.fgetc(stream)
    
14. 
    
15. def ungetc(ch, stream):
    
16.     return libc.ungetc(ch, stream)
    
17. 
    
18. # token
    
19. # [[symbol, value, rows, cols], lchild, rchild]
    
20. last_token = None
    
21. file_rows = 1
    
22. file_cols = 1
    
23. 
    
24. ERROR = 256
    
25. NUM = 257
    
26. EOF = -1
    
27. 
    
28. def error(value):
    
29.     return [[ERROR, value[1], value[2], value[3]], None, None]
    
30. 
    
31. def isdigit(ch):
    
32.     return ch >= ord('0') and ch <= ord('9')
    
33. 
    
34. def get_token():
    
35.     global last_token
    
36.     if last_token:
    
37.         result = last_token
    
38.         last_token = None
    
39.         return result
    
40.     global file_cols, file_rows
    
41.     last_position = [file_rows, file_cols]
    
42.     ch = fgetc(stdin)
    
43.     file_cols += 1
    
44.     if ch in [ord(i) for i in [' ', '\t', '\v', '\f']]:
    
45.         return get_token()
    
46.     if isdigit(ch):
    
47.         ungetc(ch, stdin)
    
48.         file_cols -= 1
    
49.         num = c_int()
    
50.         libc.fscanf(stdin, b'%d', byref(num))
    
51.         file_cols += len(str(num.value))
    
52.         return [[NUM, num.value, *last_position], None, None]
    
53.     if ch == ord('\n'):
    
54.         file_rows += 1
    
55.         file_cols = 1
    
56.     return [[ch, ch, *last_position], None, None]
    
57. 
    
58. def unget_token(token):
    
59.     global last_token
    
60.     last_token = token
    
61. 
    
62. def factor():
    
63.     token = get_token()
    
64.     if token[0][0] == NUM: return token
    
65.     if token[0][0] == ord('-'):
    
66.         token[1] = factor()
    
67.         if token[1][0][0] == ERROR: return token[1]
    
68.         return token
    
69.     if token[0][0] != ord('('): return error(token[0])
    
70.     token = expression()
    
71.     if token[0][0] == ERROR: return token
    
72.     temp = token
    
73.     token = get_token()
    
74.     if token[0][0] != ord(')'): return error(token[0])
    
75.     return temp
    
76. 
    
77. def term():
    
78.     token = factor()
    
79.     if token[0][0] == ERROR: return token
    
80.     a = token
    
81.     token = get_token()
    
82.     if token[0][0] != ord('*') and token[0][0] != ord('/'):
    
83.         unget_token(token)
    
84.         return a
    
85.     op = token
    
86.     token = term()
    
87.     if token[0][0] == ERROR: return token
    
88.     b = token
    
89.     op[1] = a
    
90.     op[2] = b
    
91.     return op
    
92. 
    
93. def expression():
    
94.     token = term()
    
95.     if token[0][0] == ERROR: return token
    
96.     a = token
    
97.     token = get_token()
    
98.     if token[0][0] != ord('+') and token[0][0] != ord('-'):
    
99.         unget_token(token)
    
100.         return a
     
101.     op = token
     
102.     token = expression()
     
103.     if token[0][0] == ERROR: return token
     
104.     b = token
     
105.     op[1] = a
     
106.     op[2] = b
     
107.     return op
     
108. 
     
109. def do_error(info):
     
110.     print('错误的表达式!', file = sys.stderr)
     
111.     print(f'(\'{chr(info[1])}\',{info[2],info[3]})', file = sys.stderr)
     
112.     while True:
     
113.         token = get_token()
     
114.         if token[0][0] == ord('\n'): break
     
115. 
     
116. def val(tree):
     
117.     if tree[0][0] == NUM: return tree[0][1]
     
118.     if tree[0][0] == ord('+'): return val(tree[1]) + val(tree[2])
     
119.     if tree[0][0] == ord('*'): return val(tree[1]) * val(tree[2])
     
120.     if tree[0][0] == ord('/'): return val(tree[1]) / val(tree[2])
     
121.     if tree[0][0] == ord('-'):
     
122.         return -val(tree[1]) if tree[2] == None else val(tree[1]) - val(tree[2])
     
123.     raise "未知的运算符!"
     
124. 
     
125. def line():
     
126.     token = get_token()
     
127.     if token[0][0] == ord('\n'): return
     
128.     unget_token(token)
     
129.     token = expression()
     
130.     if token[0][0] == ERROR:
     
131.         do_error(token[0])
     
132.         return
     
133.     result = token
     
134.     token = get_token()
     
135.     if token[0][0] == ord('\n'):
     
136.         #print(result)
     
137.         print('>>> ' + str(val(result)))
     
138.         return
     
139.     do_error(token[0])
     
140. 
     
141. def lines():
     
142.     token = get_token()
     
143.     unget_token(token)
     
144.     if token[0][0] == EOF:
     
145.         return
     
146.     line()
     
147.     lines()
     
148.     return
     
149. 
     
150. def start():
     
151.     lines()
     
152.     token = get_token()
     
153.     if token[0][0] == EOF: return True
     
154.     return False
     
155. 
     
156. print(start())
     

复制代码

参考: https://fishc.com.cn/thread-213764-1-1.html

wp231957

这东西不是用栈吗

nikezhi

用栈机制来处理括号 小甲鱼有专门讲这个的视频

傻眼貓咪

排程場演算法（或调度场算法）和逆波兰表示法
https://fishc.com.cn/thread-212875-1-1.html

ExiaGN001

中缀改成后缀（逆波兰）表达式，如果表达式合法再计算
用栈实现
具体见小甲鱼的数据结构和算法篇——栈和队列

人造人

改一下

1. print(f'(\'{chr(info[1])}\',{info[2],info[3]})', file = sys.stderr)
   
2. print(f'(\'{chr(info[1])}\', {info[2],info[3]})', file = sys.stderr)

复制代码

猫皇

感谢楼上的各位老哥，我这就去看视频。最佳答案给帮忙写了代码的老哥啦（虽然其实我用的是c++哈哈哈，不过还是很感谢您！）

hornwong