实现一个简单的计算器,输入一个包含圆括号、加、减、乘、除、求余等符号组成的算术表达式字符串,输出该算术表达式的值
时间: 2023-04-25 21:01:50 浏览: 131
可以使用栈来实现一个简单的计算器。具体步骤如下:
1. 定义两个栈,一个用来存储数字,一个用来存储运算符。
2. 遍历算术表达式字符串,对于每个字符:
- 如果是数字,将其压入数字栈中。
- 如果是左括号,将其压入运算符栈中。
- 如果是右括号,从运算符栈中弹出运算符和数字栈中弹出两个数字,进行运算,并将结果压入数字栈中,直到遇到左括号。
- 如果是运算符,将其与运算符栈顶的运算符进行比较,如果优先级较高,则将其压入运算符栈中;否则从运算符栈中弹出运算符和数字栈中弹出两个数字,进行运算,并将结果压入数字栈中,直到运算符栈顶的运算符优先级较低或者运算符栈为空。
3. 遍历完整个算术表达式字符串后,如果运算符栈不为空,则从运算符栈中弹出运算符和数字栈中弹出两个数字,进行运算,并将结果压入数字栈中,直到运算符栈为空。
4. 最终数字栈中只剩下一个数字,即为算术表达式的值。
示例:
假设算术表达式字符串为:(3+4)*5-6/2
1. 遍历字符'(',将其压入运算符栈中。
2. 遍历字符'3',将其压入数字栈中。
3. 遍历字符'+',将其与运算符栈顶的'('进行比较,优先级较高,将其压入运算符栈中。
4. 遍历字符'4',将其压入数字栈中。
5. 遍历字符')',从运算符栈中弹出'+'和数字栈中弹出两个数字3和4,进行运算3+4=7,并将结果压入数字栈中。
6. 遍历字符'*',将其与运算符栈顶的'+'进行比较,优先级较高,将其压入运算符栈中。
7. 遍历字符'5',将其压入数字栈中。
8. 遍历字符'-',将其与运算符栈顶的'*'进行比较,优先级较低,从运算符栈中弹出'*'和数字栈中弹出两个数字7和5,进行运算7*5=35,并将结果压入数字栈中。
9. 遍历字符'6',将其压入数字栈中。
10. 遍历字符'/',将其与运算符栈顶的'-'进行比较,优先级较高,将其压入运算符栈中。
11. 遍历字符'2',将其压入数字栈中。
12. 遍历完整个算术表达式字符串后,从运算符栈中弹出'/'和数字栈中弹出两个数字6和2,进行运算6/2=3,并将结果压入数字栈中。
13. 最终数字栈中只剩下一个数字35-3=32,即为算术表达式的值。
代码实现:
```python
def calculate(s: str) -> int:
stack_num = [] # 存储数字的栈
stack_op = [] # 存储运算符的栈
priority = {'+': 1, '-': 1, '*': 2, '/': 2, '%': 2} # 运算符优先级
i = 0
while i < len(s):
if s[i].isdigit(): # 如果是数字,将其压入数字栈中
j = i
while j < len(s) and s[j].isdigit():
j += 1
stack_num.append(int(s[i:j]))
i = j
elif s[i] == '(': # 如果是左括号,将其压入运算符栈中
stack_op.append(s[i])
i += 1
elif s[i] == ')': # 如果是右括号,从运算符栈中弹出运算符和数字栈中弹出两个数字,进行运算,并将结果压入数字栈中,直到遇到左括号
while stack_op[-1] != '(':
op = stack_op.pop()
num2 = stack_num.pop()
num1 = stack_num.pop()
stack_num.append(eval(str(num1) + op + str(num2)))
stack_op.pop()
i += 1
elif s[i] in priority: # 如果是运算符,将其与运算符栈顶的运算符进行比较,如果优先级较高,则将其压入运算符栈中;否则从运算符栈中弹出运算符和数字栈中弹出两个数字,进行运算,并将结果压入数字栈中,直到运算符栈顶的运算符优先级较低或者运算符栈为空
while stack_op and stack_op[-1] != '(' and priority[s[i]] <= priority[stack_op[-1]]:
op = stack_op.pop()
num2 = stack_num.pop()
num1 = stack_num.pop()
stack_num.append(eval(str(num1) + op + str(num2)))
stack_op.append(s[i])
i += 1
else:
i += 1
while stack_op: # 遍历完整个算术表达式字符串后,如果运算符栈不为空,则从运算符栈中弹出运算符和数字栈中弹出两个数字,进行运算,并将结果压入数字栈中,直到运算符栈为空
op = stack_op.pop()
num2 = stack_num.pop()
num1 = stack_num.pop()
stack_num.append(eval(str(num1) + op + str(num2)))
return stack_num[0] # 最终数字栈中只剩下一个数字,即为算术表达式的值
```
示例测试:
```python
s = '(3+4)*5-6/2'
print(calculate(s)) # 输出32
```
阅读全文