[已解决]表达式求值问题

yangzhixiaohuli

在一个表达式中，只有“(”，“)”，“0-9”，“+”，“-”，“*”，“/”，“^”，请求出表达式的值。(“/”用整数除法)。

输入格式:
共1 行，为一个算式。 （算式长度<=30 其中所有数据在 0~2^31-1的范围内）。

输出格式:
共一行，为表达式的值。

输入样例:
在这里给出一组输入。例如：

1+(3+2)*(7^2+6*9)/(2)
输出样例:
在这里给出相应的输出。例如：

258

这题用C或者C++怎么做

最佳答案

月排行榜 / 总排行榜

FishC

2024-11-1 17:58:32

要解决这个表达式求值问题，可以使用“逆波兰表达式”（RPN）或“中缀表达式转后缀表达式”的方法。以下是一个简单的思路：

1. **将中缀表达式转换为后缀表达式**：使用栈来处理运算符的优先级和括号。
2. **计算后缀表达式的值**：再次使用栈来计算后缀表达式的结果。

以下是实现这个过程的Python代码：

1. def precedence(op):
   
2.     if op == '+' or op == '-':
   
3.         return 1
   
4.     if op == '*' or op == '/':
   
5.         return 2
   
6.     if op == '^':
   
7.         return 3
   
8.     return 0
   
9. 
   
10. def apply_op(a, b, op):
    
11.     if op == '+': return a + b
    
12.     if op == '-': return a - b
    
13.     if op == '*': return a * b
    
14.     if op == '/': return a // b
    
15.     if op == '^': return a ** b
    
16. 
    
17. def evaluate(expression):
    
18.     values = []
    
19.     ops = []
    
20.     i = 0
    
21.     while i < len(expression):
    
22.         if expression[i] == ' ':
    
23.             i += 1
    
24.             continue
    
25.         elif expression[i] == '(':
    
26.             ops.append(expression[i])
    
27.         elif expression[i].isdigit():
    
28.             val = 0
    
29.             while i < len(expression) and expression[i].isdigit():
    
30.                 val = (val * 10) + int(expression[i])
    
31.                 i += 1
    
32.             values.append(val)
    
33.             i -= 1
    
34.         elif expression[i] == ')':
    
35.             while len(ops) != 0 and ops[-1] != '(':
    
36.                 val2 = values.pop()
    
37.                 val1 = values.pop()
    
38.                 op = ops.pop()
    
39.                 values.append(apply_op(val1, val2, op))
    
40.             ops.pop()
    
41.         else:
    
42.             while (len(ops) != 0 and precedence(ops[-1]) >= precedence(expression[i])):
    
43.                 val2 = values.pop()
    
44.                 val1 = values.pop()
    
45.                 op = ops.pop()
    
46.                 values.append(apply_op(val1, val2, op))
    
47.             ops.append(expression[i])
    
48.         i += 1
    
49. 
    
50.     while len(ops) != 0:
    
51.         val2 = values.pop()
    
52.         val1 = values.pop()
    
53.         op = ops.pop()
    
54.         values.append(apply_op(val1, val2, op))
    
55. 
    
56.     return values[-1]
    
57. 
    
58. # 示例
    
59. expression = "3 + 5 * (2 - 8)"
    
60. result = evaluate(expression)
    
61. print(result)

复制代码

这个代码会计算给定的算术表达式，并返回其结果。请注意，代码中使用了整数除法（`//`），以符合题目要求。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

跳转到最佳答案楼层

FishC

要解决这个表达式求值问题，可以使用“逆波兰表达式”（RPN）或“中缀表达式转后缀表达式”的方法。以下是一个简单的思路：

1. **将中缀表达式转换为后缀表达式**：使用栈来处理运算符的优先级和括号。
2. **计算后缀表达式的值**：再次使用栈来计算后缀表达式的结果。

以下是实现这个过程的Python代码：

1. def precedence(op):
   
2.     if op == '+' or op == '-':
   
3.         return 1
   
4.     if op == '*' or op == '/':
   
5.         return 2
   
6.     if op == '^':
   
7.         return 3
   
8.     return 0
   
9. 
   
10. def apply_op(a, b, op):
    
11.     if op == '+': return a + b
    
12.     if op == '-': return a - b
    
13.     if op == '*': return a * b
    
14.     if op == '/': return a // b
    
15.     if op == '^': return a ** b
    
16. 
    
17. def evaluate(expression):
    
18.     values = []
    
19.     ops = []
    
20.     i = 0
    
21.     while i < len(expression):
    
22.         if expression[i] == ' ':
    
23.             i += 1
    
24.             continue
    
25.         elif expression[i] == '(':
    
26.             ops.append(expression[i])
    
27.         elif expression[i].isdigit():
    
28.             val = 0
    
29.             while i < len(expression) and expression[i].isdigit():
    
30.                 val = (val * 10) + int(expression[i])
    
31.                 i += 1
    
32.             values.append(val)
    
33.             i -= 1
    
34.         elif expression[i] == ')':
    
35.             while len(ops) != 0 and ops[-1] != '(':
    
36.                 val2 = values.pop()
    
37.                 val1 = values.pop()
    
38.                 op = ops.pop()
    
39.                 values.append(apply_op(val1, val2, op))
    
40.             ops.pop()
    
41.         else:
    
42.             while (len(ops) != 0 and precedence(ops[-1]) >= precedence(expression[i])):
    
43.                 val2 = values.pop()
    
44.                 val1 = values.pop()
    
45.                 op = ops.pop()
    
46.                 values.append(apply_op(val1, val2, op))
    
47.             ops.append(expression[i])
    
48.         i += 1
    
49. 
    
50.     while len(ops) != 0:
    
51.         val2 = values.pop()
    
52.         val1 = values.pop()
    
53.         op = ops.pop()
    
54.         values.append(apply_op(val1, val2, op))
    
55. 
    
56.     return values[-1]
    
57. 
    
58. # 示例
    
59. expression = "3 + 5 * (2 - 8)"
    
60. result = evaluate(expression)
    
61. print(result)

复制代码

这个代码会计算给定的算术表达式，并返回其结果。请注意，代码中使用了整数除法（`//`），以符合题目要求。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。