#include<iostream>

#include<string>

#include<stack>

using namespace std;??

const int maxn=110;?

char priority[7][7]={?

? ? {'>','>','<','<','<','>','>'},??

? ? {'>','>','<','<','<','>','>'},??

? ? {'>','>','>','>','<','>','>'},??

? ? {'>','>','>','>','<','>','>'},??

? ? {'<','<','<','<','<','=','0'},? ?// 此行"("=")"表示左右括號相遇，括號內運算已完成?

? ? {'>','>','>','>','0','>','>'},??

? ? {'<','<','<','<','<','0','='}? ? // "=" 表示整個表達式求值完畢?

};? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?//? "0"表示不可能出現(xiàn)這種情況 ( 語法錯誤 )?

//Precede 用于判斷運算符棧棧頂運算符 a1 與讀入運算符 a2 之間的優(yōu)先關系函數(shù)?

char Procede(char a,char b){? ?// 建立 pre[][] 到 運算符間的映射關系?

? ? int i,j;??

? ? switch(a){??

? ? ? ? case'+':i=0;break;??

? ? ? ? case'-':i=1;break;??

? ? ? ? case'*':i=2;break;??

? ? ? ? case'/':i=3;break;??

? ? ? ? case'(':i=4;break;??

? ? ? ? case')':i=5;break;??

? ? ? ? case'#':i=6;break;? ?// # 是表達式的結束符?

? ? }??

? ? switch(b){??

? ? ? ? case'+':j=0;break;??

? ? ? ? case'-':j=1;break;??

? ? ? ? case'*':j=2;break;??

? ? ? ? case'/':j=3;break;??

? ? ? ? case'(':j=4;break;??

? ? ? ? case')':j=5;break;??

? ? ? ? case'#':j=6;break;??

? ? }??

? ? return priority[i][j];??

}

? ? ?

int Operate(int m,int n,char x){??

? ? if(x=='+')??

? ? return m+n;??

? ? if(x=='-')??

? ? return n-m;??

? ? if(x=='*')??

? ? return m*n;??

? ? if(x=='/')??

? ? return n/m;??

}??

int main(){

? ? stack <int> OPND;? // Operand stack

? ? stack <char> OPTR;? // Operator stack

OPTR.push('#');//

? ? string s;

cout<<"請輸入中綴表達式：";??

? ? cin>>s;

? ? s+="#";

? ??

? ? char c=s[0];

? ? int k=1;

? ? while(c!='#'||OPTR.top()!='#')

{? //表達式未讀完或者運算未完?

? ? ? ? int y=0;??

? ? ? ? if(c>='0'&&c<='9'){? ??

? ? ? ? ? ? while(c>='0'&&c<='9'){? // 讀入連續(xù)的數(shù)字?

? ? ? ? ? ? ? ? y=y*10+(c-'0');??

? ? ? ? ? ? ? ? c=s[k]; k++;?

? ? ? ? ? ? }??

? ? ? ? ? ? OPND.push(y);? // 把讀進的數(shù)字入數(shù)字棧?

? ? ? ? }

? ? ? ? else{

? ? ? ? ? ? switch(Procede(OPTR.top(),c))??

? ? ? ? ? ? {??

? ? ? ? ? ? ? ? case'<':? //棧頂元素優(yōu)先權低?

? ? ? ? ? ? ? ? ? ? OPTR.push(c);??

? ? ? ? ? ? ? ? ? ? c=s[k];? k++;

? ? ? ? ? ? ? ? ? ? break;??

? ? ? ? ? ? ? ? case'=':??

? ? ? ? ? ? ? ? ? ? OPTR.pop();? // 脫括號?

? ? ? ? ? ? ? ? ? ? c=s[k]; k++; // 讀入下一個字符?

? ? ? ? ? ? ? ? ? ? break;??

? ? ? ? ? ? ? ? case'>':? //退棧并將運算結果入棧?

? ? ? ? ? ? ? ? ? ? char x=OPTR.top();OPTR.pop();??

? ? ? ? ? ? ? ? ? ? int m=OPND.top();OPND.pop();??

? ? ? ? ? ? ? ? ? ? int n=OPND.top();OPND.pop();??

? ? ? ? ? ? ? ? ? ? OPND.push(Operate(m,n,x));??

? ? ? ? ? ? ? ? ? ? break;? ??

? ? ? ? ? ? }?

? ? ? ? }

? ? }

? ? cout<<"表達式的值："<<OPND.top()<<endl;

? ? return 0;

}