C++数据结构与STL--栈的应用--后缀表达式的计算

分手后的思念是犯贱 2021-12-13 00:07 246阅读 0赞

**1.后缀表达式：运算符出现在其运算数之后  
Example：  
 中缀：a+b\*c 后缀：abc\*+  
中缀：(a\*b+c)/d+e 后缀：ab\*c+d/e+  
  
  
2.后缀表达式计算  
\*从左到右扫描后缀表达式的每一项，用一个栈装载运算数，如果是运算数将其推入栈  
\*如果是二元运算符，则出栈两运算数，并计算结果，再把结果压人栈中  
Example：计算后缀表达式435\*+  
step1-step3:  
![Center][]  
step4：  
![Center 1][]  
step5:  
![Center 2][]  
  
  
  
  
实现代码：仅演示原理，并未包含异常处理  
 //判断是否为数字   
bool isDigt(const char &c)  
\{   
 if(c>='0'&&c<='9')  
 return true;  
  
 return false;  
\}  
  
  
  
  
//判断是否为操作符  
bool isOperator(const char &c)  
\{   
if(c=='+'||c=='-'||c=='\*'||c=='/')  
 return true;  
  
 return false;  
\}   
  
  
//从栈中取两个操作数   
void getOperands(stack<int> &st,int& oprand1,int& oprand2)  
\{   
oprand1=st.top();  
st.pop();  
oprand2=st.top();  
st.pop();  
\}  
  
  
//计算两操作数的值   
int compute(int& oprand1,int& oprand2,char op)   
\{   
int res=0;  
switch(op)  
\{   
case '+':  
 res=oprand1+oprand2;  
 break;  
 case '-':  
 res=oprand1-oprand2;  
 break;  
case '\*':  
 res=oprand1\*oprand2;  
 break;  
 default:  
 res=oprand1/oprand2;  
  
  
\}   
  
return res;  
  
\}  
  
  
  
  
int main()  
\{   
stack<int> st;  
string expr("435\*+");  
int oprand1=0; //记录操作数1   
int oprand2=0; //记录操作数2  
int res=0; //记录结果   
for(int i=0;i<expr.size();i++) //从左到右扫描后缀表达式的每一项   
\{   
if(isDigt(expr\[i\])) //如果是运算数将其推入栈  
\{   
st.push(expr\[i\]-'0');  
\}  
else if(isOperator(expr\[i\])) //如果是二元运算符，则出栈两运算数，  
\{ //并计算结果，再把结果压人栈中  
 getOperands(st,oprand1,oprand2);  
 st.push(compute(oprand1,oprand2,expr\[i\]));  
\}  
\}  
  
res=st.top();  
cout<<res<<endl; //19  
\}**

[Center]: /images/20211210/f83fe86dcebb4f519e1c74cc7a1b99d4.png
[Center 1]: /images/20211210/1e4a11f03ab345bdb5557225ce62adae.png
[Center 2]: /images/20211210/7d595786792d49f2a1090764a87da3f9.png