/* 將中綴表達(dá)式(a+b)轉(zhuǎn)換為后綴表達(dá)式(ab+)的算法思想：  
   ·當(dāng)讀到數(shù)字直接送至輸出隊(duì)列中  
   ·當(dāng)讀到運(yùn)算符t時(shí)，  
      a.將棧中所有優(yōu)先級(jí)高于或等于t的運(yùn)算符彈出，送到輸出隊(duì)列中；    
      b.t進(jìn)棧  
   ·讀到左括號(hào)時(shí)總是將它壓入棧中  
   ·讀到右括號(hào)時(shí)，將靠近棧頂?shù)牡谝粋€(gè)左括號(hào)上面的運(yùn)算符全部依次彈出，送至輸出隊(duì)列后，再丟棄左括號(hào)。  
  
      運(yùn)用后綴表達(dá)式進(jìn)行計(jì)算的具體做法：  
   ·建立一個(gè)棧S  
   ·從左到右讀后綴表達(dá)式，讀到數(shù)字就將它轉(zhuǎn)換為數(shù)值壓入棧S中，讀到運(yùn)算符則從棧中依次彈出兩個(gè)數(shù)分別到Y和X，然后以“X   運(yùn)算符   Y”的形式計(jì)算機(jī)出結(jié)果，再壓加棧S中  
   ·如果后綴表達(dá)式未讀完，就重復(fù)上面過程，最后輸出棧頂?shù)臄?shù)值則為結(jié)束 */

#include <iostream>
#include <string>
using namespace std;

char ex[100];//存儲(chǔ)后綴表達(dá)式
char str[100];//存儲(chǔ)算術(shù)表達(dá)式
char stack[100];//作為棧使用
char ch;//當(dāng)前判斷的字符
int i=0;//i為算術(shù)表達(dá)式str的下標(biāo)
int t;//t為后綴式ex的下標(biāo)
int top=0;//top為棧頂
void trans();//轉(zhuǎn)換函數(shù)
void compute();//計(jì)算后綴式的值

void trans()//將中綴式轉(zhuǎn)換為后綴式
{
cout<<"輸入一個(gè)算術(shù)表達(dá)式，以#號(hào)結(jié)束："<<endl;
while(str[i]!='#')//中綴式以#號(hào)結(jié)束
{
   i++;//因?yàn)?span lang="EN-US">i的初值設(shè)為0
   cin>>str[i];
}

//開始掃描
t=1;
i=1;
ch=str[i];
i++;//i指向當(dāng)前掃描字符的下一位
while(ch!='#')//逐個(gè)掃描，直至遇到#號(hào)結(jié)束
{
   switch(ch)
   {
   case'('://遇到（，進(jìn)棧
    top++;
    stack[top]=ch;
    break;
   case')'://遇到），將靠近棧頂?shù)牡谝粋€(gè)左括號(hào)上面的運(yùn)算符全部依次彈出，送至后綴式隊(duì)列后，再丟棄左括號(hào)。
    while(stack[top]!='(')
    {
     ex[t]=stack[top];
     top--;
     t++;
    }
    top--;//丟棄（
    break;
   case'+':
   case'-':
    while(top!=0 && stack[top]!='(')
    {
     ex[t]=stack[top];
     top--;
     t++;
    }
    top++;//因?yàn)?span lang="EN-US">top的初值為0
    stack[top]=ch;
    break;
   case'*':
   case'/':
    while(stack[top]=='*'|| stack[top]=='/')
   {
    ex[t]=stack[top];
    top--;
    t++;
   }
   top++;
   stack[top]=ch;
   break;
 
   /*注意！除操作數(shù)外，其它符號(hào)都要用到棧*/
   default:while(ch>='0' && ch<='9')//遇到操作數(shù)直接送至后綴式隊(duì)列
     {
      ex[t]=ch;
      t++;
      ch=str[i];
      i++;//此時(shí)i指向操作數(shù)之后的運(yùn)算符的后一位！！
     }
    i--;//要在操作數(shù)之后，運(yùn)算符之前添加空格符
    ex[t]=' ';//用空格符隔開
    t++;

   }//switch結(jié)束

   ch=str[i];//仿照default中的，返回添加空格符之前的操作
   i++;
}//結(jié)束while

while(top!=0)//仍有運(yùn)算符在棧中
{
   ex[t]=stack[top];
   t++;
   top--;
}
ex[t]=' ';//不能省，若省掉則無法進(jìn)入compute函數(shù)??

for(int j=1;j<i-1;j++)
   cout<<str[j];
cout<<"的后綴式為：";
for(j=1;j<t;j++)
cout<<ex[j];

}

void compute()
{
float stack[100];//作為棧使用
int d;//用于存放當(dāng)前的計(jì)算結(jié)果
char ch;
int t=1;
int top =0;
ch=ex[t];
t++;

while(ch!=' ')//此空格符為后綴式中的最后一個(gè)字符，與上文中的" ex[t]=' '; "相對(duì)應(yīng)
{
   switch(ch)
   {
   case'+':
    stack[top-1]=stack[top-1]+stack[top];
    top--;
    break;
   case'-':
    stack[top-1]=stack[top-1]-stack[top];
    top--;
    break;
   case'*':
    stack[top-1]=stack[top-1]*stack[top];
    top--;
    break;
   case'/':
    if(stack[top]!=0)
     stack[top-1]=stack[top-1]/stack[top];
    else
    {
     cout<<"\n除零錯(cuò)誤!"<<endl;
     exit(0);//異常退出
    }
    top--;//兩個(gè)操作數(shù)算出一個(gè)結(jié)果存放到棧頂，那兩操作數(shù)便可丟棄，故top-1
    break;
   default:
    d=0;
    while(ch>='0' && ch<='9')
    {
     d=10*d+ch-'0';//將數(shù)字字符轉(zhuǎn)化為對(duì)應(yīng)的數(shù)值，*10是與大于10的數(shù)值時(shí)要進(jìn)位
     ch=ex[t];
     t++;
    }
    top++;
    stack[top]=d;//棧頂存放當(dāng)前計(jì)算結(jié)果
 
   }//switch結(jié)束
   ch=ex[t];//跳過空格符，掃描下一個(gè)運(yùn)算符或操作數(shù)
   t++;
}
cout<<"\n計(jì)算結(jié)果為:"<<stack[top]<<endl;
}

void main()
{
trans();
compute();
}

結(jié)果如圖所示：