假定我們需要計(jì)算的表達(dá)式是一個(gè)類似這樣的形式
1-(3+2)*7-9/3+(1+2)*3
和一般的簡單計(jì)算不一樣，這是一種混合運(yùn)算甚至包含括號击孩，所以我們的具體計(jì)算過程并不是從左到右的迫悠，而是有優(yōu)先級判斷的
基于這樣一種情況，開始計(jì)算前作如下調(diào)整
將首尾各加一個(gè)符號用做識別溯壶，比如’#’及皂，那么原式變成#1-(3+2)*7-9/3+(1+2)*3#，接下來初始化兩個(gè)棧且改，stack1（用做存數(shù)字）验烧，stack2（用做存運(yùn)算符）
首先將表達(dá)式第一個(gè)字符即#壓入stack2，然后依次掃描表達(dá)式又跛，遇到數(shù)字就直接壓入stack1碍拆，若遇到運(yùn)算符，作如下處理
將stack2棧頂?shù)姆柡蛼呙璧降姆栠M(jìn)行優(yōu)先級判斷：
若棧頂運(yùn)算符的優(yōu)先級低于剛掃描到的運(yùn)算符的優(yōu)先級，則讓剛掃描到的運(yùn)算符入棧
若棧頂運(yùn)算符的優(yōu)先級高于剛掃描到的運(yùn)算符的優(yōu)先級感混，則將stack2棧頂運(yùn)算符退棧端幼，同時(shí)stack1棧頂?shù)臄?shù)字連續(xù)退棧兩次，將兩個(gè)退棧的數(shù)字和一個(gè)退棧的運(yùn)算符進(jìn)行相應(yīng)運(yùn)算弧满，將結(jié)果重新壓入stack1（注意此時(shí)不一定能將剛掃描到的運(yùn)算符入棧婆跑，有可能存在stack2棧頂連續(xù)多個(gè)運(yùn)算符的優(yōu)先級比剛掃描到的運(yùn)算符優(yōu)先級高，所以這一步需要一直計(jì)算到stack2棧頂運(yùn)算符的優(yōu)先級不比剛掃描到的運(yùn)算符的優(yōu)先級高為止庭呜，此時(shí)才能將剛掃描到的運(yùn)算符壓入stack2）
若棧頂運(yùn)算符的優(yōu)先級等于剛掃描到的運(yùn)算符的優(yōu)先級滑进，則說明左右括號相遇，將stack2棧頂運(yùn)算符退棧即可
重復(fù)以上操作募谎，直到stack2棧頂元素和剛掃描到的運(yùn)算符均為’#’時(shí)扶关，說明表達(dá)式掃描完畢，此時(shí)stack1棧頂數(shù)字即為結(jié)果
算符優(yōu)先關(guān)系如下圖所示
?最左邊的一列為棧頂運(yùn)算符数冬，最上面的一行為剛掃描到的運(yùn)算符节槐，Error表示這兩個(gè)運(yùn)算符在表達(dá)式正常的情況下不會遇到，如果遇到可能是表達(dá)式有誤
下面模擬一個(gè)最簡單的例子的運(yùn)行過程拐纱，例如3-2+4
首先將表達(dá)式變形為#3-2+4#,初始化stack1铜异，stack2
#3-2+4#
#壓入stack2
stack1 = []
stack2 = [#]
3-2+4#
3壓入stack1
stack1 = [3]
stack2 = [#]
-2+4#
#和-判斷優(yōu)先級，# < -戳玫，-壓入stack2
stack1 =[3]
stack2 = [#,-]
2+4#
2壓入stack1
stack1 = [3,2]
stack2 = [#,-]
+4#
-和+判斷熙掺，- > +未斑，取出3咕宿，2和-，進(jìn)行3-2運(yùn)算將結(jié)果壓入stack1
stack1 = [1]
stack2 = [#]
+4#
#和+判斷蜡秽，# < +府阀，+壓入stack2
stack1 = [1]
stack2 = [#,+]
4#
4壓入stack1
stack1 = [1,4]
stack2 = [#,+]
#
+和#判斷，+ > #芽突，取出1试浙，4和+，進(jìn)行1+4運(yùn)算將結(jié)果壓入stack1
stack1 = [5]
stack2 = [#]
#
#和#相遇寞蚌，表達(dá)式求值完畢田巴，結(jié)果為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))
