表达式分为前缀(DLR)、中缀(LDR)、后缀表达式(LRD)三种。
我们平时使用的基本都是中缀表达式，形如$1 + 2 + 4 * 5$
而前缀表达式又称波兰式，如$+ + 1 2 * 4 5(上式转化而来)$
后缀表达式又称逆波兰式，如$12+45*+$

在这三种表达式中，所有的叶子节点都一定是数字，非叶子节点则为运算符号。

前缀表达式(含小数)计算

分析

由于是前缀表达式，所以必然是先有运算符，后有数字的，所以我们从后往前遍历，每读完一个数字就压入栈中，当读到运算符时，就将栈顶的两个元素取出，计算结果并将值压入栈中，最终栈内剩下的一个元素就是最终答案。

C++ 代码

#include<bits/stdc++.h>
using namespace std;
stack<double> stk;
bool calc(char c)
{
    double a,b;
    a = stk.top();
    stk.pop();
    b = stk.top();
    stk.pop();
    if(c=='+') a+=b;
    if(c=='-') a-=b;
    if(c=='*') a*=b;
    if(c=='/')
    {
        if(b==0) return false;
        else a/=b;
    }
    stk.push(a);    
    return true;
}
int main()
{
    string s;
    getline(cin, s);
    for (int i = s.size() - 1; i >= 0; i--) //倒序遍历
    {
        if(s[i]==' ') continue;
        else if(isdigit(s[i]))  //如果是数字
        {
            double mul=10,num=s[i]-'0'; //计算当前的小数是多少
            for (int j=i-1; j >= 0; j--)
            {
                if (isdigit(s[j]))
                {
                    num += (s[j] - '0') * mul;
                    mul *= 10;
                }
                else if(s[j]=='.')  //遇到小数点，让之前的结果num/乘数mul,同时mul重置1
                {
                    num /= mul;
                    mul = 1;
                }
                else if(s[j]=='-')  //如果是负数，就*-1
                    num*=-1;
                else{
                    i=j;
                    break;
                }
            }
            stk.push(num);      //当前数压入栈中
        }
        else    //为运算符
        {
            if(!calc(s[i]))     //如果b为0，即除数为0，则无法进行运算
            {
                puts("ERROR");
                return 0;
            }
        }
    }
    printf("%.1lf", stk.top());
}

后缀表达式计算(不带括号)

分析

后缀表达式中数字一定在前面，所以从前往后进行计算。每读完一个数字就压入栈中，当读到运算符时，要对运算符的优先级进行判断，当前栈顶运算符优先级>=当前运算符时，就进行运算，最终栈内剩下的一个元素就是最终答案。

C++ 代码

class Solution {
public:
    bool digit(char p)
    {
        if(p>='0' && p<='9') return true;
        return false;
    }    
    unordered_map<char,int> pri;
    stack<int> stk;
    stack<char> op;
    void eval() //进行计算
    {
        int a=stk.top(); stk.pop();
        int b=stk.top(); stk.pop();
        char c=op.top(); op.pop();
        if(c=='+') b=b+a;
        if(c=='-') b=b-a;
        if(c=='*') b=b*a;
        if(c=='/') b=b/a;
        stk.push(b);
    }
    int calculate(string s) {
        pri['+']=pri['-']=1;    //*  / 的优先级比+ -要大
        pri['*']=pri['/']=2;

        for(int i=0;i<s.size();i++)
        {
            if(s[i]==' ') continue;
            else if(digit(s[i])){
                int num=0,j=i;
                while(j<s.size() && digit(s[j]))
                {
                    num=num*10+(s[j]-'0');
                    j++;
                }
                stk.push(num);  //将数压入栈中
                i=j-1;
            }
            else{
                while(op.size() && pri[op.top()]>=pri[s[i]]) eval();    //栈顶运算符优先级>=当前运算符
                op.push(s[i]);
            }
        }
        while(op.size())
        {
            eval();
        }
        return stk.top();
    }
};

后缀表达式计算(带括号计算)

分析

其实带括号与不带括号的区别就在于要优先将括号里的结果计算出来,其他操作完全一样。

1. 遇到左括号’(‘，直接压入栈中。
2. 遇到右括号’)’,开始遍历字符栈，将栈内的字符进行运算操作，直到遇见’(‘,操作结束后要将’(‘弹出
3. 其他操作完全相同

C++ 代码

#include<bits/stdc++.h>
using namespace std;
string s;
stack<int> stk1;
stack<char> stk2;
unordered_map<char,int> pri;
int getc(char c)
{
    if(c=='+') return 1;
    if(c=='-') return 2;
    if(c=='*') return 3;
    if(c=='/') return 4;
}
void eval() //计算结果
{
    auto a=stk1.top(); stk1.pop();
    auto b=stk1.top(); stk1.pop();
    int c=getc(stk2.top()); stk2.pop();
    // cout<<a<<" "<<b<<" "<<c<<endl;
    if(c==1) b+=a;
    if(c==2) b-=a;
    if(c==3) b*=a;
    if(c==4) b/=a;    
    stk1.push(b);
}
int main()
{
    pri['+']=pri['-']=1;    //为运算符设置优先级
    pri['*']=pri['/']=2;
    cin>>s;
    for(int i=0;i<s.size();i++)
    {
        if(isdigit(s[i]))   //压入数字栈stk1
        {
            int temp=0,j=i;
            while(j<s.size() && isdigit(s[j]))
            {
                temp=10*temp+(s[j]-'0');
                j++;
            }
            stk1.push(temp);
            i=j-1;
        }
        else if(s[i]=='(') stk2.push(s[i]); //将左括号'('压入栈中
        else if(s[i]==')')      //遇到了右括号')'，需要将'('到')'之间的所有运算符都进行运算
        {
            while(stk2.size() && stk2.top()!='(')
            {
                eval();
            }
            stk2.pop();     //跳出循环后,让'('出栈
        }
        else{
            while(stk2.size() && pri[stk2.top()]>=pri[s[i]]) eval();    //比较运算符优先级，进行运算
            stk2.push(s[i]);
        }
    }
    while(stk2.size()) eval();  //将字符栈的运算全部计算完
    cout<<stk1.top();   //数字栈顶元素即为答案
    return 0;
}