/* 將中綴表達式(a+b)轉換為后綴表達式(ab+)的算法思想：
·當讀到數字直接送至輸出隊列中
·當讀到運算符t時，
a.將棧中所有優先級高于或等于t的運算符彈出，送到輸出隊列中；
b.t進棧
·讀到左括號時總是將它壓入棧中
·讀到右括號時，將靠近棧頂的第一個左括號上面的運算符全部依次彈出，送至輸出隊列后，再丟棄左括號。
運用后綴表達式進行計算的具體做法：
·建立一個棧S
·從左到右讀后綴表達式，讀到數字就將它轉換為數值壓入棧S中，讀到運算符則從棧中依次彈出兩個數分別到Y和X，然后以“X 運算符 Y”的形式計算機出結果，再壓加棧S中
·如果后綴表達式未讀完，就重復上面過程，最后輸出棧頂的數值則為結束 */
#include <iostream>
#include <string>
using namespace std;
char ex[100];//存儲后綴表達式
char str[100];//存儲算術表達式
char stack[100];//作為棧使用
char ch;//當前判斷的字符
int i=0;//i為算術表達式str的下標
int t;//t為后綴式ex的下標
int top=0;//top為棧頂
void trans();//轉換函數
void compute();//計算后綴式的值
void trans()//將中綴式轉換為后綴式
{
cout<<"輸入一個算術表達式，以#號結束："<<endl;
while(str[i]!='#')//中綴式以#號結束
{
i++;//因為i的初值設為0
cin>>str[i];
}
//開始掃描
t=1;
i=1;
ch=str[i];
i++;//i指向當前掃描字符的下一位
while(ch!='#')//逐個掃描，直至遇到#號結束
{
switch(ch)
{
case'('://遇到（，進棧
top++;
stack[top]=ch;
break;
case')'://遇到），將靠近棧頂的第一個左括號上面的運算符全部依次彈出，送至后綴式隊列后，再丟棄左括號。
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++;//因為top的初值為0
stack[top]=ch;
break;
case'*':
case'/':
while(stack[top]=='*'|| stack[top]=='/')
{
ex[t]=stack[top];
top--;
t++;
}
top++;
stack[top]=ch;
break;
/*注意！除操作數外，其它符號都要用到棧*/
default:while(ch>='0' && ch<='9')//遇到操作數直接送至后綴式隊列
{
ex[t]=ch;
t++;
ch=str[i];
i++;//此時i指向操作數之后的運算符的后一位！！
}
i--;//要在操作數之后，運算符之前添加空格符
ex[t]=' ';//用空格符隔開
t++;
}//switch結束
ch=str[i];//仿照default中的，返回添加空格符之前的操作
i++;
}//結束while
while(top!=0)//仍有運算符在棧中
{
ex[t]=stack[top];
t++;
top--;
}
ex[t]=' ';//不能省，若省掉則無法進入compute函數??
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;//用于存放當前的計算結果
char ch;
int t=1;
int top =0;
ch=ex[t];
t++;
while(ch!=' ')//此空格符為后綴式中的最后一個字符，與上文中的" ex[t]=' '; "相對應
{
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除零錯誤!"<<endl;
exit(0);//異常退出
}
top--;//兩個操作數算出一個結果存放到棧頂，那兩操作數便可丟棄，故top-1
break;
default:
d=0;
while(ch>='0' && ch<='9')
{
d=10*d+ch-'0';//將數字字符轉化為對應的數值，*10是與大于10的數值時要進位
ch=ex[t];
t++;
}
top++;
stack[top]=d;//棧頂存放當前計算結果
}//switch結束
ch=ex[t];//跳過空格符，掃描下一個運算符或操作數
t++;
}
cout<<"\n計算結果為:"<<stack[top]<<endl;
}
void main()
{
trans();
compute();
}
結果如圖所示：
