關(guān)于后綴表達(dá)式的java實(shí)現(xiàn)過(guò)程

第關(guān)于后綴表達(dá)式的java實(shí)現(xiàn)過(guò)程目錄中綴表示法java實(shí)現(xiàn)后綴表示法逆波蘭表達(dá)式的計(jì)算方式與中綴記法的轉(zhuǎn)換java后綴表達(dá)式的計(jì)算實(shí)現(xiàn)方法示例代碼實(shí)現(xiàn)

中綴表示法java實(shí)現(xiàn)

觀察一個(gè)普通的算式：3+4*5

我們當(dāng)然知道，應(yīng)該先計(jì)算4*5再將這個(gè)結(jié)果和3相加，就能得到最后的結(jié)果。

如果是一個(gè)復(fù)雜一些的算式：3+4*（（5-6）/7+8）

這依然難不倒我們，只要牢記（）的優(yōu)先級(jí)最高，然后是*/，最后是+-就沒(méi)問(wèn)題了，這就是通常的中綴表示法。

但是通過(guò)算法分析，這樣的表達(dá)式，由于每一次都需要判斷優(yōu)先級(jí)，所以運(yùn)行的時(shí)間應(yīng)當(dāng)是O（N^2）。

在表達(dá)式很長(zhǎng)很復(fù)雜的時(shí)候，就需要一種更適合計(jì)算機(jī)的算法來(lái)計(jì)算了。

后綴表示法

簡(jiǎn)介

逆波蘭表示法（ReversePolishnotation，RPN，或逆波蘭記法），是一種是由波蘭數(shù)學(xué)家揚(yáng)武卡謝維奇1920年引入的數(shù)學(xué)表達(dá)式方式，在逆波蘭記法中，所有操作符置于操作數(shù)的后面，因此也被稱為后綴表示法。

逆波蘭記法不需要括號(hào)來(lái)標(biāo)識(shí)操作符的優(yōu)先級(jí)。逆波蘭記法中，操作符置于操作數(shù)的后面。

例如表達(dá)三加四時(shí)，寫(xiě)作34+，而不是3+4。如果有多個(gè)操作符，操作符置于第二個(gè)操作數(shù)的后面，所以常規(guī)中綴記法的3-4+5在逆波蘭記法中寫(xiě)作34-5+：先3減去4，再加上5。維基百科逆波蘭表示法詞條。

這種表示法有以下特點(diǎn)：

不需要使用括號(hào)。和中綴表達(dá)式不同，逆波蘭表達(dá)式不需要遍歷整個(gè)算式來(lái)尋找一對(duì)括號(hào)。逆波蘭表達(dá)式的實(shí)現(xiàn)一般基于堆棧。在計(jì)算機(jī)中，堆棧這種數(shù)據(jù)結(jié)構(gòu)具有極快的效率。運(yùn)行時(shí)間是O（N）。不滿足交換律。

逆波蘭表達(dá)式的計(jì)算方式

例如2*3+4*5

你可以這么計(jì)算，2和3相乘的和是5，把這個(gè)數(shù)存起來(lái)，再計(jì)算4*5的值，存起來(lái)，最后在計(jì)算兩個(gè)存在一起的值。寫(xiě)出來(lái)是這樣子的23*45*+。這就是后綴或逆波蘭記法。

采用堆棧實(shí)現(xiàn)的過(guò)程很簡(jiǎn)單，規(guī)則如下。

從頭開(kāi)始讀取。讀取到如果是數(shù)字，則將其壓入棧中。如果是一個(gè)符號(hào)，就取兩次棧頂?shù)脑赝ㄟ^(guò)該符號(hào)進(jìn)行計(jì)算，再把得到的數(shù)壓入棧中。

Java實(shí)現(xiàn)

publicclassPRNCalculator{

publicstaticdoublePRNCal(StringPRN){

StackDoublestack=newStackDouble

String[]ss=PRN.split("");

for(inti=0;iss.length;i++){

if(ss[i].matches("\\d"))stack.push(Double.valueOf(ss[i]));

if(ss[i].matches("[+|-|*|/]")){

doubleb=stack.pop();

doublea=stack.pop();

if(ss[i].equals("+"))stack.push(a+b);

if(ss[i].equals("-"))stack.push(a-b);

if(ss[i].equals("*"))stack.push(a*b);

if(ss[i].equals("/"))stack.push(a/b);

}

}

returnstack.pop();

}

}

Test類

publicclassPRNTest{

publicstaticvoidmain(String[]args){

Strings="23*45*+";

doubleresult=PRNCalculator.PRNCal(s);

System.out.println("輸入的逆波蘭表達(dá)式:"+s);

System.out.println("計(jì)算結(jié)果:"+result);

}

}

打印結(jié)果：

輸入的逆波蘭表達(dá)式:23*45*+

計(jì)算結(jié)果:26.0

與中綴記法的轉(zhuǎn)換

和后綴表達(dá)式的計(jì)算方法類似，一個(gè)中綴記法轉(zhuǎn)換到后綴記法，也可以利用堆棧來(lái)實(shí)現(xiàn)。

從頭開(kāi)始讀取。如果讀取到的是數(shù)字，將其輸出。如果讀取到的是符號(hào)，則判斷該符號(hào)的優(yōu)先級(jí)是否高于棧頂或棧為空，是，則壓入棧中；否，則將棧頂輸出并繼續(xù)判斷。如果讀取到的是括號(hào)，(會(huì)直接被壓入棧；在讀取到)的時(shí)候，棧會(huì)一直彈出直到遇到(。下面是這個(gè)轉(zhuǎn)換的Java實(shí)現(xiàn)。

packagePRNCalculator;

importjava.util.Stack;

publicclassPRNCalculator{

publicstaticStringPRNTansf(Strings){

StackStringstack=newStackString

String[]ss=s.split("");

StringBuffersb=newStringBuffer();

for(inti=0;iss.length;i++){

if(ss[i].matches("\\d"))sb.append(ss[i]+"");

if(ss[i].matches("[+|-|*|/|(|)]")){

if(stack.isEmpty()){

stack.push(ss[i]);

}else{

if(ss[i].matches("[+|-]")){

while(!stack.isEmpty()!stack.peek().matches("[(]"))sb.append(stack.pop()).append("");

if(stack.isEmpty()||stack.peek().matches("[(]"))stack.push(ss[i]);

}

if(ss[i].matches("[*|/]")){

while(stack.peek().matches("[*|/]")!stack.peek().matches("[(]"))sb.append(stack.pop()).append("");

if(stack.isEmpty()||stack.peek().matches("[(]")||stack.peek().matches("[+|-]"))stack.push(ss[i]);

}

if(ss[i].matches("[(]")){

stack.push(ss[i]);

}

if(ss[i].matches("[)]")){

while(!stack.peek().matches("[(]"))sb.append(stack.pop()).append("");

if(stack.peek().matches("[(]"))stack.pop();

}

}

}

}

while(!stack.isEmpty())sb.append(stack.pop()).append("");

returnsb.toString();

}

}

*Test類*

packagePRNCalculator;

publicclassPRNTest{

publicstaticvoidmain(String[]args){

Strings="4+5+8*(6+8*7)/3+4";

StringPRN=PRNCalculator.PRNTansf(s);

System.out.println("輸入的表達(dá)式為：");

System.out.println(s);

System.out.println("輸出的逆波蘭表達(dá)式為：");

System.out.println(PRN);

doubleresult=PRNCalculator.PRNCal(PRN);

System.out.println("該表達(dá)式計(jì)算結(jié)果為：");

System.out.println(result);

}

}

打印結(jié)果：

輸入的表達(dá)式為：

4+5+8*(6+8*7)/3+4

輸出的逆波蘭表達(dá)式為：

45+8687*+*3/+4+

該表達(dá)式計(jì)算結(jié)果為：

178.33333333333334

java后綴表達(dá)式的計(jì)算

實(shí)現(xiàn)方法

從左至右掃描表達(dá)式

遇到數(shù)字時(shí)，將數(shù)字壓棧，遇到運(yùn)算符時(shí)，彈出棧頂?shù)膬蓚€(gè)數(shù)，計(jì)算并將結(jié)果入棧

重復(fù)2直到表達(dá)式最右端，最后運(yùn)算得出的值即為表達(dá)式的結(jié)果

示例

計(jì)算后綴表達(dá)式的值：123+4+5-

從左至右掃描，將1，2，3壓入棧；

遇到+運(yùn)算符，3和2彈出，計(jì)算2+3的值，得到5，將5壓入棧；

遇到4，將4壓入棧

遇到運(yùn)算符，彈出4和5，計(jì)算54的值，得到20，將20壓入棧；

遇到+運(yùn)算符，彈出20和1，計(jì)算1+20的值，得到21，將21壓入棧；

遇到5，將5壓入棧；

遇到-運(yùn)算符，彈出5和21，計(jì)算21-5的值，得到16為最終結(jié)果

代碼實(shí)現(xiàn)

publicclassReversePolishNotation{

publicstaticvoidmain(String[]args){

Stringnotation="1023+4*+5-";

ReversePolishNotationreversePN=newReversePolishNotation();

StackIntegernumStack=newStack();

//以空格分隔上述表達(dá)式，存到數(shù)組中

String[]s=notation.split("");

//遍歷數(shù)組

for(inti=0;is.length;i++){

if(!reversePN.isOperator(s[i])){

//如果不是運(yùn)算符，則壓棧

numStack.push(Integer.parseInt(s[i]));

}