1、后序表达式求值：

后续表达式(逆波兰式)的特点：没有括号。

求值方法：

从前向后扫，

遇到操作数压栈；

遇到操作符，从栈中取出2个操作数运算，结果压栈。

最终栈中所剩的数为结果。

2、中序表达式求值

我们先来定义运算符的优先级：

(

+,-

*,/,%

从上到下依次升高

准备2个栈，一个专门存放运算符，另一个专门存放操作数。

1.遇到)，那么退栈计算到(为止.结果压栈。

2.遇到运算数.那么压栈。

3.如果当前运算符优先级低于栈顶运算符.那么计算栈顶运算符并将结果压栈.

4.否则压栈.

计算带括号和浮点数的表达式：

#include
      
            #include
       
             #include
        
              #include
         
               using namespace std;        typedef string::size_type it;        char Compare(char op,char ch)    //优先级比较      {        if((op=='#'&&ch=='#')||(op=='('&&ch==')')) return '=';        if(ch=='#') return '<';        if(op=='#') return '>';        if(op=='(') return '>';        if(ch==')') return '<';        if(ch=='(') return '>';        if(ch=='*'||ch=='/')         if(op=='+'||op=='-') return '>';        else return '<';        if(ch=='+'||ch=='-') return '<';    }        void modify(string& s)   //优化表达式      {        string s1="()+-*/";        for(it i=0;i
          
            ch;        bool valid=true;        for(it i=0;i
           
            & num,stack
            
             & ops,const string & s) { string s1="()+-*/#"; it i=0; while(i
             
              ') ops.push(ch); else if(Compare(op,ch)=='=') ops.pop(); else { while(1) { char c=ops.top(); if(Compare(c,ch)=='>') { ops.push(ch); break; } else if(Compare(c,ch)=='=') { ops.pop(); break; } else { char optr=ops.top(); ops.pop(); double n1=num.top(); num.pop(); double n2=num.top(); num.pop(); double value; if(optr=='+') value=n2+n1; if(optr=='-') value=n2-n1; if(optr=='*') value=n2*n1; if(optr=='/') { double E=0.00001; if( n1>-E && n1
              
                num; stack 
               
                 ops; ops.push('#'); string s; cout<<"Input the string:"<
               
              
             
            
           
          
         
        
       
      

将中序表达式转换成后序表达式（逆波兰表达式）的算法：

(1)初始化一个空的运算符栈

(2)在没有到达中缀表达式的结尾及没有发生错误的时候，执行以下步骤：

 1.获取表达式中的一个标记（常数、变量、算术运算符，左括号，右括号）。

 2.如果标记是：

   i.  一个左括号，将其压入栈中

   ii. 一个右括号，连续弹出并显示栈中的元素，直到遇到一个左括号，不要显示这个左括号。（如果直到栈为空还没遇到一个左括号，则是一个错误）

   iii.一个运算符，如果栈为空，或者标记具有比栈顶元素更高的优先级，则将其压入栈中。否则出并显示栈顶的元素，接着继续比较标记和新的栈顶元素。（运算符比左括号的优先级高）

   iv 一个操作数，显示它

(3)当到达中缀表达式的结尾时，弹出并显示栈中的元素直到栈为空为止。

参考代码：

//将表达式转化为逆波兰表达式   string RPN(const string& exp)   {        char token,toptoken;        stack
      
        oper;        string RPNexp;        int length=exp.length();        for(int i=0;i
       

num; int num1,num2,value; int length=exp.length(); for(int i=0;i