C语言逆波兰式实现表达式计算器

#include<iostream> #include<cstdlib> #define STACK_INIT_SIZE 10; //#define STACKINCREMENT 10; using namespace std; typedef struct { //构造栈 char* top; char* base; int stacksize; }Stack; int JudegPri(char c,Stack s,char a[7],char b[7][7]); //优先级判断函数 bool JudgeOperate(char c,char a[7]); //运算符判断函数 bool InitStack(Stack &s) //栈的初始化 { s.base=(char*)malloc(15*sizeof(char));//初始空间分配 if(!s.base) return 0; s.top=s.base; s.stacksize=STACK_INIT_SIZE;//栈大小初始化 return 1; } char push(Stack &s,char e)//压栈 { *s.top++=e; } char pop(Stack &s,char e)//出栈 { e=*--s.top; } char GetTop(Stack s,char e)//获取栈顶元素 { if(s.top==s.base) return 0; e=*(s.top-1); return e; } int main() //主函数 { Stack s;// 构造栈Stack的对象 s InitStack(s);//调用栈初始化函数 bool flag=1; //栈为空的标志,1表示非空 bool sign=1; int label =0; char c;//当前元素 char e;//栈顶元素 char a[7]={'+','-','*','/','#','(',')'};//用#替代↑ char b[7][7]={ {'=','=','<','<','<','>','>'}, //运算符优先级关系矩阵 {'=','=','<','<','<','<','>'}, {'>','>','=','=','<','<','>'}, {'>','>','=','=','<','<','>'}, {'>','>','>','>','=','<','>'}, {'<','<','<','<','<','=','='}, {'<','<','<','<','<',' ','='} }; loop: cout<<"请输入中缀运算表达式,以$结尾"<<endl; while(flag) { sign=1; cin>>c; //输入一个字符 if(c=='$') //字符等于$时，表示输入串为空 { while(s.top!=s.base) //栈不空 { cout<<pop(s,e)<<" "; //退栈输出 } flag=0; //栈为空的标志 } // if(c==' ') else if(!JudgeOperate(c,a))//(c!=' ')//如果是运算符 { if(c=='(') { label++; push(s,c); } else if(s.top!=s.base) //栈不空 { if(JudegPri(c,s,a,b))//是运算符 、栈也不空，判断输入符号优先级高于当前栈顶符号优先级 push(s,c); else //判断输入符号优先级是否高于当前栈顶符号优先级 if(c==')') //输入符号是')' { label--; while(sign) { if(GetTop(s,e)=='(') //栈顶符号是'(' { pop(s,e); //退栈 sign=0; // } else { if(s.top==s.base) //栈空 { cout<<"error!"; sign=0; flag==0; } else cout<<pop(s,e)<<" ";//退栈输出 } }//while(sign) }// if(c==')') 输入符号是“)” else { cout<<pop(s,e);//退栈输出 ,应该继续判断栈是否为空 //及优先级，如果不空，优先级不高就出栈 ，否则进栈 while(s.top!=s.base&&(!JudegPri(c,s,a,b))) cout<<pop(s,e)<<" "; push(s,c); } } // if(s.top!=s.base) //栈不空 else push(s,c); //栈空 ,运算符进栈 } //if(JudgeOperate(c,a)) else cout<<c<<" ";//如果不是运算符，直接输出 } cout<<endl; if(label!=0) {cout<<"Input Error ! Try Again! "<<endl; label=0; flag=1; goto loop; } system("pause"); } int JudegPri(char c,Stack s,char a[7],char b[7][7])//判断优先级，若当前优先级高返回1 ，否则返回0 { char e; int k,d; for(int i=0;i<7;i++) { if(a[i]==c) //当前运算符 k=i; if(a[i]==GetTop(s,e)) //栈顶运算符 d=i; } if(b[k][d]=='>')//若当前运算符优先级高，返回1 return 1; else return 0;//否则，返回0 } bool JudgeOperate(char c,char a[7])//判断是不是运算符 ，是返回0，否则返回1 { bool signal=1; for(int j=0;j<7;j++) if(c==a[j]) //是运算符时，标记 signal=0 signal=0; return signal; //否则，标记 signal=1 }