数据结构栈实现四则运算

例如，计算9+(3-1)*3+8/2

思路：通过栈来实现上述元素，我们一般称上述表达式为中缀表达式，我们首先要将其转换为后缀表达式，因为中缀表达式不利于计算机运算。

上代码： 算法思路： 对字符串中的内容，遇到数字就输出，遇到符号则与栈顶元素比较优先级，若低，则将栈顶元素弹栈，若高，则压栈。若为右括号，则连续输出，直到遇到左括号，这输出的就是后缀表达式 其中isp()和icp()这两个函数是对于优先级的规定，在下一段代码中有它们的定义

void postfix(){ stack<char> s; char y; // s.makeEmpty(); s.push('#'); char ch[20]="9+(3-1)*3+8/2"; for(int i=0;i<13;i++){ if(isdigit(ch[i])) cout<<ch[i]; else if(ch[i]==')'){ // cout<<ch[i]<<endl; while(!(s.empty())&&(y=s.top())!='('){ cout<<y; s.pop(); } if(!s.empty()) s.pop(); } else{ while(!s.empty()&&isp(y=s.top())>icp(ch[i])){ cout<<y; s.pop(); } s.push(ch[i]); } } while(!s.empty()){ cout<<s.top(); s.pop(); } }

有了后缀表达式，我们需要的是计算，我们做的是，遇数字压栈，与符号则弹出前两个数进行计算，将结果入栈。

#include<cmath> #include<stack> #include<iostream> using namespace std; int isp(char ch){ switch(ch){ case '#': return 0; case '(': return 1; case '^': return 7; case '*': case '/': case '%': return 5; case '+': case '-': return 3; case ')': return 8; } } int icp(char ch){ switch(ch){ case '#': return 0; case '(': return 8; case '^': return 6; case '*': case '/': case '%': return 4; case '+': case '-': return 3; case ')': return 1; } } class Calculator{ public: Calculator(){} double Run(); void Clear(); private: void AddOperand(double value); bool Get2Operands(double &left,double &right); void DoOperator(char op); stack<double> s; }; void Calculator::AddOperand(double value){ s.push(value); } void Calculator::Clear(){ } bool Calculator::Get2Operands(double &left,double &right){ if(s.empty()){ cerr<<"Missing Operands!"<<endl; return false; } right = s.top(); s.pop(); if(s.empty()){ cerr<<"Missing Operands!"<<endl; return false; } left = s.top(); s.pop(); return true; } void Calculator::DoOperator(char op){ double left,right; bool result; result = Get2Operands(left,right); if(result==true){ switch(op){ case '+': s.push(left+right); break; case '-': s.push(left-right); break; case '*': s.push(left*right); break; case '/': if(abs(right)<=1E-6){ cerr<<"Divide By 0"<<endl; Clear(); } else s.push(left/right); break; /* case '^': s.push(left^right); break;*/ } } else{ Clear(); } } double Calculator::Run(){ char ch; double newoperand,ret; while(cin>>ch,ch!='='){ switch( ch ) { case '+': case '-': case '*': case '/': case '^': DoOperator(ch); break; default: cin.putback(ch); cin >> newoperand; AddOperand(newoperand); break; } } ret = s.top(); s.pop(); return ret; } int main(){ // postfix(); Calculator c; double ans = c.Run(); cout<<ans; return 0; }