假定我们需要计算的表达式是一个类似这样的形式
1-(3+2)*7-9/3+(1+2)*3
和一般的简单计算不一样，这是一种混合运算甚至包含括号，所以我们的具体计算过程并不是从左到右的，而是有优先级判断的
基于这样一种情况，开始计算前作如下调整
将首尾各加一个符号用做识别，比如’#’，那么原式变成#1-(3+2)*7-9/3+(1+2)*3#，接下来初始化两个栈，stack1（用做存数字），stack2（用做存运算符）
首先将表达式第一个字符即#压入stack2，然后依次扫描表达式，遇到数字就直接压入stack1，若遇到运算符，作如下处理
将stack2栈顶的符号和扫描到的符号进行优先级判断：
若栈顶运算符的优先级低于刚扫描到的运算符的优先级，则让刚扫描到的运算符入栈
若栈顶运算符的优先级高于刚扫描到的运算符的优先级，则将stack2栈顶运算符退栈，同时stack1栈顶的数字连续退栈两次，将两个退栈的数字和一个退栈的运算符进行相应运算，将结果重新压入stack1（注意此时不一定能将刚扫描到的运算符入栈，有可能存在stack2栈顶连续多个运算符的优先级比刚扫描到的运算符优先级高，所以这一步需要一直计算到stack2栈顶运算符的优先级不比刚扫描到的运算符的优先级高为止，此时才能将刚扫描到的运算符压入stack2）
若栈顶运算符的优先级等于刚扫描到的运算符的优先级，则说明左右括号相遇，将stack2栈顶运算符退栈即可
重复以上操作，直到stack2栈顶元素和刚扫描到的运算符均为’#’时，说明表达式扫描完毕，此时stack1栈顶数字即为结果
算符优先关系如下图所示
算符关系图
最左边的一列为栈顶运算符，最上面的一行为刚扫描到的运算符，Error表示这两个运算符在表达式正常的情况下不会遇到，如果遇到可能是表达式有误
下面模拟一个最简单的例子的运行过程，例如3-2+4
首先将表达式变形为#3-2+4#,初始化stack1，stack2
#3-2+4#
#压入stack2
stack1 = []
stack2 = [#]
3-2+4#
3压入stack1
stack1 = [3]
stack2 = [#]
-2+4#
#和-判断优先级，# < -，-压入stack2
stack1 =[3]
stack2 = [#,-]
2+4#
2压入stack1
stack1 = [3,2]
stack2 = [#,-]
+4#
-和+判断，- > +，取出3，2和-，进行3-2运算将结果压入stack1
stack1 = [1]
stack2 = [#]
+4#
#和+判断，# < +，+压入stack2
stack1 = [1]
stack2 = [#,+]
4#
4压入stack1
stack1 = [1,4]
stack2 = [#,+]
#
+和#判断，+ > #，取出1，4和+，进行1+4运算将结果压入stack1
stack1 = [5]
stack2 = [#]
#
#和#相遇，表达式求值完毕，结果为stack1栈顶元素5
python源码
import re
def calculate(expression):
stack1 = []
stack2 = []
stack2.append('#')
expression = expression + '#'
for i in expression:
a = re.match(r'\d+',i)
if(a != None):
stack1.append(a.group(0))
else:
if(judgement(stack2[len(stack2)-1],i) == '<'):
stack2.append(i)
elif(judgement(stack2[len(stack2)-1],i) == '>'):
while(judgement(stack2[len(stack2)-1],i) == '>'):
operator = stack2.pop()
operand1 = stack1.pop()
operand2 = stack1.pop()
if(operator == '+'):
stack1.append(float(operand1) + float(operand2))
elif(operator == '-'):
stack1.append(float(operand2) - float(operand1))
elif(operator == '*'):
stack1.append(float(operand1) * float(operand2))
elif(operator == '/'):
stack1.append(float(operand2) / float(operand1))
if(i == ')'):
stack2.pop()
else:
stack2.append(i)
return stack1.pop()
def judgement(str1,str2):
dictionary1 = {'+':'>','-':'>','*':'<','/':'<','(':'<',')':'>','#':'>'}
dictionary2 = {'+':'>','-':'>','*':'<','/':'<','(':'<',')':'>','#':'>'}
dictionary3 = {'+':'>','-':'>','*':'>','/':'>','(':'<',')':'>','#':'>'}
dictionary4 = {'+':'>','-':'>','*':'>','/':'>','(':'<',')':'>','#':'>'}
dictionary5 = {'+':'<','-':'<','*':'<','/':'<','(':'<',')':'=','#':'error'}
dictionary6 = {'+':'>','-':'>','*':'>','/':'>','(':'error',')':'>','#':'>'}
dictionary7 = {'+':'<','-':'<','*':'<','/':'<','(':'<',')':'error','#':'='}
dictionary8 = {'+':dictionary1,
'-':dictionary2,
'*':dictionary3,
'/':dictionary4,
'(':dictionary5,
')':dictionary6,
'#':dictionary7}
return dictionary8[str1][str2]
a = '1-(3+2)*7-9/3+(1+2)*3'
print(calculate(a))
网友评论