用顺序栈实现用户输入一个包含“+”、“-”、“*”、“/”、正整数和圆括号的合法数学表达式,计算该表达式的运算结果。
时间: 2023-11-05 13:58:07 浏览: 67
好的,我会回答你的问题。首先,我们需要将中缀表达式转换成后缀表达式才能计算结果。可以使用栈来实现这一转换过程。
步骤如下:
1. 新建一个栈s1和一个空字符串s2。
2. 从左到右遍历中缀表达式的每个数字或符号:
a. 如果是数字或小数点,直接添加到字符串s2中。
b. 如果是左括号,将其推入栈s1中。
c. 如果是右括号,将栈s1中的符号依次弹出并加入到字符串s2中,直到遇到左括号为止。
d. 如果是运算符,将其和栈s1中的符号进行比较,若栈s1为空或栈顶为左括号,将其推入栈s1中。否则,将栈s1中的符号弹出并加入到字符串s2中,直到遇到优先级小于等于该运算符的符号为止,然后将该运算符推入栈s1中。
3. 遍历完中缀表达式后,将栈s1中剩余的符号依次弹出并加入到字符串s2中。
4. 新建一个栈s3,从左到右遍历后缀表达式的每个数字或符号:
a. 如果是数字或小数点,将其转换成浮点数后推入栈s3中。
b. 如果是运算符,弹出栈s3的两个数字进行该运算,然后将计算结果推入栈s3中。
5. 遍历完后缀表达式后,栈s3中剩余的数字即为表达式的计算结果。
代码实现如下(假设输入的中缀表达式为字符串exp):
```python
# 定义运算符优先级
priority = {'*':2, '/':2, '+':1, '-':1, '(':0}
# 中缀表达式转后缀表达式
s1, s2 = [], ''
for c in exp:
if c.isdigit() or c=='.':
s2 += c
elif c == '(':
s1.append(c)
elif c == ')':
while s1 and s1[-1]!='(':
s2 += s1.pop()
s1.pop() # 弹出左括号
else: # 运算符
while s1 and priority[c]<=priority[s1[-1]]:
s2 += s1.pop()
s1.append(c)
while s1:
s2 += s1.pop()
# 后缀表达式计算结果
s3 = []
for c in s2:
if c.isdigit() or c=='.':
s3.append(float(c))
else:
b, a = s3.pop(), s3.pop() # 注意先弹出的是被减数/被除数
if c == '+':
s3.append(a+b)
elif c == '-':
s3.append(a-b)
elif c == '*':
s3.append(a*b)
else:
s3.append(a/b)
result = s3.pop()
```
注意:以上代码只适用于表达式中没有负数、括号没有嵌套且没有多余的空格的情况。如果需要支持这些情况,代码需要进一步修改。
阅读全文