第詳解Java中綴表達式的實現(xiàn)目錄1.概念2.算法流程3代碼實現(xiàn)

1.概念

什么是中綴表達式，什么是后綴表達式

從小學開始學習的四則運算，例如：3+(5*(2+3)+7)類似這種表達式就是中綴表達式。中綴表達式人腦很容易理解，各個算符的優(yōu)先級，人腦也很容易判斷，先算括弧里的，再算*，再算+，-

但是這種表達式很不利于計算機計算，通過某種方式把前綴表達式轉(zhuǎn)換為后綴表達式方便計算機進行計算，如3+(5*(2+3)+7)的后綴表達式就是3,5,2,3,+,*,7,+,+。這個表達式計算機很容易計算，為什么容易計算，通過算法流程2，就會一個深入的理解。

2.算法流程

如何把中綴表達式轉(zhuǎn)換成后綴表達式比如說3+(5*(2+3)+7)的轉(zhuǎn)成后綴表達式的流程如何？

操作符優(yōu)先級:

+,-小于*，/+等于-*等于/

左括號和右括號作為特殊操作符特殊處理。(碰到(不用判斷優(yōu)先級直接入操作符棧，碰到),也不用判斷優(yōu)先級,直接出操作符棧)

大致算法掌握以下幾個流程：

準備兩個棧，一個是數(shù)字棧A，一個是操作符棧(+,-,*,/(,))B等

1.0對于數(shù)字棧A，遇到數(shù)字直接入棧A。

2.0對于操作符棧B，分幾種情況

2.1碰到(操作符直接入棧

2.2碰到)操作符，不停的把操作符棧B出棧，直到遇到)。（把(到)之間的彈出的操作符依次入棧A）

2.3碰到+,-,*/比較當前元素（假設(shè)當前元素current）和B棧棧頂?shù)牟僮鞣?假設(shè)棧頂元素是top)的優(yōu)先級.

2.3.1如果top=current,B棧出棧且循環(huán)比較，直到topcurrent退出循環(huán)，且把current入棧

2.3.2如果topcurrent,直接把current入B棧

3.0掃描完整個字符串，如果B棧中還有操作符，依次出棧入A

按照上面算法演示3+(5*(2+3)+7)的流程：

1，碰到3，3入A棧[3,]

2，碰到+，入B棧[+,]

3，碰到(，入B棧[+,(]

4，碰到5，入A棧[3,5]

5，碰到*，*的優(yōu)先級大于(,入B棧[+,(,*]

6，碰到(,入B棧[+,(,*,(]

7，碰到2，入A棧[3,5,2]

8，碰到+,入B棧[+,(,*,(,+]

9，碰到3，入A棧[3,5,2,3]

10，碰到),彈出B棧，直接到(，把彈出的操作符入A棧。B:[+,(,*]A:[3,5,2,3,+]

11，碰到+,+的優(yōu)先級小于B的棧頂元素*，所以*從B出棧，入A,并把+入B。B:[+,(,+]A:[3,5,2,3,+,*]

12，碰到7，入A棧[3,5,2,3,+,*,7]

13，碰到),彈出B棧，直接到(，把彈出的操作符入A棧。B:[+]A:[3,5,2,3,+,*,7,+]

14,掃描完整個字符串，判斷B是否為空，不為空把B棧的元素彈出，入A。當前不為空，所以最終A棧的元素為A:[3,5,2,3,+,*,7,+,+]

所以最終A的后綴表達式是3,5,2,3,+,*,7,+,+

計算機拿到這個會怎么計算呢？流程如下：

碰到數(shù)字直接入棧碰到操作符，直接彈出兩個棧頂元素，通過操作符計算，把結(jié)果壓入棧

通過步驟1，2循環(huán)計算，最終棧里只會有一個元素，這個就是表達式的結(jié)果。

我們來演練一下：

1,碰到數(shù)字3,5,2,3直接入棧A[3,5,2,3]

2,碰到+，彈出棧頂2，3，相加得5入棧A[3,5,5]

3,碰到*，彈出棧頂5，5，相乘得25入棧A[3,25]

4,碰到7，直接入棧A[3,25,7]

5,碰到+，彈出棧頂25，7，相加得32入棧A[3,32]

6,碰到+，彈出棧頂3，32，相加得35入棧A[35]

通過上面可以得知，計算機很容易計算，從左掃描到右就能把結(jié)果得出。

3代碼實現(xiàn)

mid2post求后綴表達式

calcPostExp拿到后綴表達式求值

cmpPriority優(yōu)先級比較

//優(yōu)先級

boolcmpPriority(chartop,charcur)//比較當前字符與棧頂字符的優(yōu)先級，若棧頂高，返回true

if((top=='+'||top=='-')(cur=='+'||cur=='-'))

returntrue;

if((top=='*'||top=='/')(cur=='+'||cur=='-'||top=='*'||top=='/'))

returntrue;

if(cur==')')

returntrue;

returnfalse;

求后綴表達式求值

vectorstringmid2post(stringstr)

vectorstringvstr;

stackcharcstack;

for(inti=0;istr.size();++i)//掃描字符串

stringtemp="";

if(str[i]='0'str[i]='9')//若是數(shù)字

temp+=str[i];

while(i+1str.size()str[i+1]='0'str[i+1]='9')

temp+=str[i+1];//若是連續(xù)數(shù)字

++i;

vstr.push_back(temp);

elseif(cstack.empty()||str[i]=='(')//若?？栈蛘咦址麨?('

cstack.push(str[i]);

elseif(cmpPriority(cstack.top(),str[i]))//若棧頂元素優(yōu)先級較高，棧頂元素出棧

if(str[i]==')')//若當前字符是右括號，棧中元素出棧，入字符串數(shù)組中，直到遇到'('

while(!cstack.empty()cstack.top()!='(')

temp+=cstack.top();

cstack.pop();

vstr.push_back(temp);

temp="";

cstack.pop();

else//棧中優(yōu)先級高的元素出棧，入字符串數(shù)組，直到優(yōu)先級低于當前字符

while(!cstack.empty()cmpPriority(cstack.top(),str[i]))

temp+=cstack.top();

cstack.pop();

vstr.push_back(temp);

temp="";

cstack.push(str[i]);

else//當前字符優(yōu)先級高于棧頂元素，直接入棧

cstack.push(str[i]);

while(!cstack.empty())//棧中還存在運算符時，出棧，存入字符串數(shù)組

stringtemp="";

temp+=cstack.top();

cstack.pop();

vstr.push_back(temp);

returnvstr;

對后綴表達式進行求值，主要是根據(jù)運算符取出兩

intcalcPostExp(vectorstringvstr)//對后綴表達式進行求值，主要是根據(jù)運算符取出兩個操作數(shù)進行運算

intnum,op1,op2;

stackintopstack;

for(inti=0;ivstr.size();++i)

stringtemp=vstr[i];

if(temp[0]='0'temp[0]='9')//如果當前字符串是數(shù)字，利用字符串流轉(zhuǎn)化為int型

stringstreamss;

sstemp;

ssnum;

opstack.push(num);

elseif(vstr[i]=="+")//若是操作符，取出兩個操作數(shù)，進行運算，并將結(jié)果存入

op2=opstack.top();

opstack.pop();

op1=opstack.top();

opstack.pop();

opstack.push(op1+op2);

elseif(vstr[i]=="-")

op2=opstack.top();

opstack.pop();

op1=opstack.top();

opstack.pop();

opstack.push(op1-op2);

elseif(vstr[i]=="*")

op2=opstack.top();

opstack.pop();

op1=opstack.top();

opstack.pop();