第帶你了解Java數(shù)據(jù)結(jié)構(gòu)和算法之前綴,中綴和后綴表達(dá)式目錄1、人如何解析算術(shù)表達(dá)式①、求值3+4-5②、求值3+4*52、計(jì)算機(jī)如何解析算術(shù)表達(dá)式3、后綴表達(dá)式①、如何將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式？一、先自定義一個(gè)棧二、前綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式三、測(cè)試四、結(jié)果五、分析②、計(jì)算機(jī)如何實(shí)現(xiàn)后綴表達(dá)式的運(yùn)算？4、前綴表達(dá)式①、如何將中綴表達(dá)式轉(zhuǎn)換為前綴表達(dá)式？②、計(jì)算機(jī)如何實(shí)現(xiàn)前綴表達(dá)式的運(yùn)算？總結(jié)

1、人如何解析算術(shù)表達(dá)式

如何解析算術(shù)表達(dá)式？或者換種說法，遇到某個(gè)算術(shù)表達(dá)式，我們是如何計(jì)算的：

①、求值3+4-5

這個(gè)表達(dá)式，我們?cè)诳吹?+4后都不能直接計(jì)算3+4的值，知道看到4后面的-號(hào)，因?yàn)闇p號(hào)的優(yōu)先級(jí)和前面的加號(hào)一樣，所以可以計(jì)算3+4的值了，如果4后面是*或者/，那么就要在乘除過后才能做加法操作，比如：

②、求值3+4*5

這個(gè)不能先求3+4的值，因?yàn)?后面的*運(yùn)算級(jí)別比前面的+高。通過這兩個(gè)表達(dá)式的說明，我們可以總結(jié)解析表達(dá)式的時(shí)候遵循的幾條規(guī)則：

①、從左到右讀取算式。②、已經(jīng)讀到了可以計(jì)算值的兩個(gè)操作數(shù)和一個(gè)操作符時(shí)，可以計(jì)算，并用計(jì)算結(jié)果代替那兩個(gè)操作數(shù)和一個(gè)操作符。③、繼續(xù)這個(gè)過程，從左到右，能算就算，直到表達(dá)式的結(jié)尾。

2、計(jì)算機(jī)如何解析算術(shù)表達(dá)式

對(duì)于前面的表達(dá)式3+4-5，我們?nèi)耸怯兴季S能力的，能根據(jù)操作符的位置，以及操作符的優(yōu)先級(jí)別能算出該表達(dá)式的結(jié)果。但是計(jì)算機(jī)怎么算？

計(jì)算機(jī)必須要向前（從左到右）來讀取操作數(shù)和操作符，等到讀取足夠的信息來執(zhí)行一個(gè)運(yùn)算時(shí)，找到兩個(gè)操作數(shù)和一個(gè)操作符進(jìn)行運(yùn)算，有時(shí)候如果后面是更高級(jí)別的操作符或者括號(hào)時(shí)，就必須推遲運(yùn)算，必須要解析到后面級(jí)別高的運(yùn)算，然后回頭來執(zhí)行前面的運(yùn)算。我們發(fā)現(xiàn)這個(gè)過程是極其繁瑣的，而計(jì)算機(jī)是一個(gè)機(jī)器，只認(rèn)識(shí)高低電平，想要完成一個(gè)簡(jiǎn)單表達(dá)式的計(jì)算，我們可能要設(shè)計(jì)出很復(fù)雜的邏輯電路來控制計(jì)算過程，那更不用說很復(fù)雜的算術(shù)表達(dá)式，所以這樣來解析算術(shù)表達(dá)式是不合理的，那么我們應(yīng)該采取什么辦法呢？

請(qǐng)大家先看看什么是前綴表達(dá)式，中綴表達(dá)式，后綴表達(dá)式：這三種表達(dá)式其實(shí)就是算術(shù)表達(dá)式的三種寫法，以3+4-5為例

①、前綴表達(dá)式：操作符在操作數(shù)的前面，比如+-543②、中綴表達(dá)式：操作符在操作數(shù)的中間，這也是人類最容易識(shí)別的算術(shù)表達(dá)式3+4-5③、后綴表達(dá)式：操作符在操作數(shù)的后面，比如34+5-

上面我們講的人是如何解析算術(shù)表達(dá)式的，也就是解析中綴表達(dá)式，這是人最容易識(shí)別的，但是計(jì)算機(jī)不容易識(shí)別，計(jì)算機(jī)容易識(shí)別的是前綴表達(dá)式和后綴表達(dá)式，將中綴表達(dá)式轉(zhuǎn)換為前綴表達(dá)式或者后綴表達(dá)式之后，計(jì)算機(jī)能很快計(jì)算出表達(dá)式的值，那么中綴表達(dá)式是如何轉(zhuǎn)換為前綴表達(dá)式和后綴表達(dá)式，以及計(jì)算機(jī)是如何解析前綴表達(dá)式和后綴表達(dá)式來得到結(jié)果的呢？

3、后綴表達(dá)式

后綴表達(dá)式，指的是不包含括號(hào)，運(yùn)算符放在兩個(gè)運(yùn)算對(duì)象的后面，所有的計(jì)算按運(yùn)算符出現(xiàn)的順序，嚴(yán)格從左向右進(jìn)行（不再考慮運(yùn)算符的優(yōu)先規(guī)則）。

由于后綴表達(dá)式的運(yùn)算符在兩個(gè)操作數(shù)的后面，那么計(jì)算機(jī)在解析后綴表達(dá)式的時(shí)候，只需要從左向右掃描，也就是只需要向前掃描，而不用回頭掃描，遇到運(yùn)算符就將運(yùn)算符放在前面兩個(gè)操作符的中間（這里先不考慮乘方類似的單目運(yùn)算），一直運(yùn)算到最右邊的運(yùn)算符，那么就得出運(yùn)算結(jié)果了。既然后綴表達(dá)式這么好，那么問題來了：

①、如何將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式？

對(duì)于這個(gè)問題，轉(zhuǎn)換的規(guī)則如下：

一、先自定義一個(gè)棧

packagecom.ys.poland;

publicclassMyCharStack{

privatechar[]array;

privateintmaxSize;

privateinttop;

publicMyCharStack(intsize){

this.maxSize=size;

array=newchar[size];

top=-1;

//壓入數(shù)據(jù)

publicvoidpush(charvalue){

if(topmaxSize-1){

array[++top]=value;

//彈出棧頂數(shù)據(jù)

publiccharpop(){

returnarray[top--];

//訪問棧頂數(shù)據(jù)

publiccharpeek(){

returnarray[top];

//查看指定位置的元素

publiccharpeekN(intn){

returnarray[n];

//為了便于后面分解展示棧中的內(nèi)容，我們?cè)黾恿艘粋€(gè)遍歷棧的方法(實(shí)際上棧只能訪問棧頂元素的)

publicvoiddisplayStack(){

System.out.print("Stack(bottom--top):");

for(inti=0;itop+1;i++){

System.out.print(peekN(i));

System.out.print('');

System.out.println("");

//判斷棧是否為空

publicbooleanisEmpty(){

return(top==-1);

//判斷棧是否滿了

publicbooleanisFull(){

return(top==maxSize-1);

}

二、前綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式

packagecom.ys.poland;

publicclassInfixToSuffix{

privateMyCharStacks1;//定義運(yùn)算符棧

privateMyCharStacks2;//定義存儲(chǔ)結(jié)果棧

privateStringinput;

//默認(rèn)構(gòu)造方法，參數(shù)為輸入的中綴表達(dá)式

publicInfixToSuffix(Stringin){

input=in;

s1=newMyCharStack(input.length());

s2=newMyCharStack(input.length());

//中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式，將結(jié)果存儲(chǔ)在棧中返回，逆序顯示即后綴表達(dá)式

publicMyCharStackdoTrans(){

for(intj=0;jinput.length();j++){

System.out.print("s1棧元素為：");

s1.displayStack();

System.out.print("s2棧元素為：");

s2.displayStack();

charch=input.charAt(j);

System.out.println("當(dāng)前解析的字符:"+ch);

switch(ch){

case'+':

case'-':

gotOper(ch,1);

break;

case'*':

case'/':

gotOper(ch,2);

break;

case'(':

s1.push(ch);//如果當(dāng)前字符是'(',則將其入棧

break;

case')':

gotParen(ch);

break;

default:

//1、如果當(dāng)前解析的字符是操作數(shù)，則直接壓入s2

//2、

s2.push(ch);

break;

}//endswitch

}//endfor

while(!s1.isEmpty()){

s2.push(s1.pop());

returns2;

publicvoidgotOper(charopThis,intprec1){

while(!s1.isEmpty()){

charopTop=s1.pop();

if(opTop=='('){//如果棧頂是'(',直接將操作符壓入s1

s1.push(opTop);

break;

}else{

intprec2;

if(opTop=='+'||opTop=='-'){

prec2=1;

}else{

prec2=2;

if(prec2prec1){//如果當(dāng)前運(yùn)算符比s1棧頂運(yùn)算符優(yōu)先級(jí)高，則將運(yùn)算符壓入s1

s1.push(opTop);

break;

}else{//如果當(dāng)前運(yùn)算符與棧頂運(yùn)算符相同或者小于優(yōu)先級(jí)別，那么將S1棧頂?shù)倪\(yùn)算符彈出并壓入到S2中

//并且要再次再次轉(zhuǎn)到while循環(huán)中與s1中新的棧頂運(yùn)算符相比較；

s2.push(opTop);

}//endwhile

//如果s1為空，則直接將當(dāng)前解析的運(yùn)算符壓入s1

s1.push(opThis);

//當(dāng)前字符是')'時(shí)，如果棧頂是'(',則將這一對(duì)括號(hào)丟棄，否則依次彈出s1棧頂?shù)淖址瑝喝雜2，直到遇到'('

publicvoidgotParen(charch){

while(!s1.isEmpty()){

charchx=s1.pop();

if(chx=='('){

break;

}else{

s2.push(chx);

}

三、測(cè)試

@Test

publicvoidtestInfixToSuffix(){

Stringinput;

System.out.println("Enterinfix:");

Scannerscanner=newScanner(System.in);

input=scanner.nextLine();

InfixToSuffixin=newInfixToSuffix(input);

MyCharStackmy=in.doTrans();

my.displayStack();

}

四、結(jié)果

五、分析

②、計(jì)算機(jī)如何實(shí)現(xiàn)后綴表