如何用栈完成表达式计算？
如何用栈完成表达式计算？
///////////////////////////////
///表达式计算////数据结构:栈////作者：ZZJ_4Ever
///////////////////////////////
#include<iostream>#include<stack>#include<string>#include<assert.h>usingnamespacestd;stack<double>data_stack;stack<char>char_stack;intPRI(char&ch){
if(ch==')'){return1;}elseif(ch=='+'||ch=='-'){return2;}elseif(ch=='*'||ch=='/'){return3;}elsereturn0;}/*2.扫描到操作符,与操作符栈的顶端操作符进行比较,如果优先级小或相等,则弹出数据和操作符进行计算,将结果送入数据栈;如果优先级较大,则进操作符栈;如果是’(‘直接进栈,如果是’)’,遇到’(‘则抵消.*/voidExc_stack(){doubleresult_temp;assert(char_stack.size()>=1&&data_stack.size()>=1);doubletemp1=data_stack.top();data_stack.pop();doubletemp2=data_stack.top();data_stack.pop();charpopchar=char_stack.top();char_stack.pop();if(popchar=='+')result_temp=temp2+temp1;elseif(popchar=='-')result_temp=temp2-temp1;elseif(popchar=='*')result_temp=temp2*temp1;elseif(popchar=='/')result_temp=temp2/temp1;data_stack.push(result_temp);}voidpush_charinto(char&ch){if(ch=='(')//如果是’(‘直接进栈char_stack.push(ch);elseif(char_stack.empty()){char_stack.push(ch);
}elseif(PRI(ch)>PRI(char_stack.top()))//如果优先级较大,则进操作符栈{char_stack.push(ch);}//扫描到操作符else//如果优先级小或相等,则弹出数据和操作符进行计算,将结果送入数据栈{Exc_stack();if(ch==')')//如果是’)’,遇’(‘直接弹出.{while(char_stack.top()!='(')//操作括号内的内容直到遇到'('为止{Exc_stack();}char_stack.pop();}else//将自己压入栈char_stack.push(ch);}}voidpush_datainto(double&db){data_stack.push(db);}voidmain(){stringstr;while(1){boolflag=false;doubleret=0.0;doublen;cout<<"在此输入表达式:";//读入cin>>str;//处理//筛选/////////////////////////////开始扫描///////////////////////for(inti=0;i<str.length();i++){if(str[i]>='0'&&str[i]<='9'){if(!flag)ret=ret*10+str[i]-'0';else{ret=ret+(str[i]-'0')/n;n*=10;}}elseif(str[i]=='.'){n=10;flag=true;}else{if(ret!=0||str[i-1]=='0')push_datainto(ret);ret=0.0;flag=false;push_charinto(str[i]);}}//如果最后一个数字还没有压入栈if(ret!=0||str[i-1]=='0')push_datainto(ret);//3.扫描数据完成后,依次退栈并进行计算assert(!data_stack.empty()||!char_stack.empty());while(data_stack.size()!=1){Exc_stack();}//doublerre=data_stack.top();cout<<"结果:"<<data_stack.top()<<endl;data_stack.pop();}}