每日算法_表达式求值&逆波兰表达式求值

先来看一道力扣上比较简单的， 题目链接 : 150. 逆波兰表达式求值

根据 逆波兰表示法，求表达式的值。

有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

说明：

整数除法只保留整数部分。
给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

这里简单说下逆波兰表示式(也叫后缀表达式)， 详细了解点上面链接去百度百科, 来看下面的式子：

(2+2)*(1+1)            // 这是我们平常看的表达式, 这也叫中缀表达式
2 2 + 1 1 + *          // 这个是后缀表达式，可以发现其并没有括号，那么后缀表达式是如何计算的?  

求解后缀表达式， 我们可以将其转化为表达式树的形式， 即上面的后缀表达式其实是表达式树后序遍历的结果。 故我们利用该后缀表达式重新建树得 ， 看下图求解表达式树的过程

其实我们发现表达式数的前序遍历,中序遍历和后续遍历结果即为前缀表达式、中缀表达式(若不对自加括号)、后缀表达式, 这里是根据后缀表达式作为表达式树的后序遍历的结果，我们重建的树如上图所示，可以发现每个子树根节点均为一个运算符， 而对每一个子树的运算结果
result = (左子树) (其父节点根节点运算符[“+”, “-“, ” * “, ” / ” ] ) (右子树), 具体见上图的两步变换过程.

但我们有必要针对每一个后缀表达式都进行建树操作然后进行这样的计算吗？ 显然通过上面的运算过程我们发现， 后缀表达式中 2 2 + 1 1 + * 从左到右遍历当遇到一个运算符时，其左边的必然有两个操作数， 且这两个操作数与这个运算符的运算结果即为上图左子树或者右子树的部分， 当我们运算完序列就变成了 4 1 1 + * , 当遇到+号时，同样也是取其左边两个操作数进行相加操作，运算后结果为 4 2 * , 然后遇到 * 号， 左边的两个数进行相乘操作， 最后得到结果为8， 我们发现这个过程只涉及在一端的加入和删除操作，这不就符合我们栈的数据的进出结构， 故我们对于后缀表达式，我们的处理步骤为:

1. 若遇到数字直接进行进栈操作

2.遇到运算符 op( +, - , *, /)，先出栈一个数，记为n2, 在出栈一个数记为n1, 然后进行运算其结果为result = n1 op n2; 然后将result结果进栈

3. 直到将后缀表达式遍历完，此时栈中只有一个元素,即我们的运算结果，若不是一个数，那么这个后缀表示式是错误的。

！注意我们这里进行运算的时候先出栈的数是n2, 后出栈的是n1, 这里主要是考虑减法操作和除法操作。

C++代码实现

class Solution 
{
public:
    stack<int> st;                               // 栈用于保存我们中间的运算和最后的结果
    void eval(string &s)                         // 这个函数用于进行求值, 通过判断此时的运算符执行相应的操作,最后将运算结果压栈
    {
        int n2 = st.top();st.pop();
        int n1 = st.top();st.pop();
        if(s == "+") st.push(n1 + n2);
        else if(s == "-") st.push(n1 - n2);
        else if(s == "*") st.push(n1 * n2);
        else st.push(n1 / n2);
    }

    int evalRPN(vector<string>& tokens)                      
    {
        unordered_set<string> S = {"+", "-", "*", "/"};       // 表示一个运算符集合, 方便下面不用写很长的if判断
        for(auto &s: tokens)                                  // 遍历我们的后缀表示式
        {
            if(S.count(s)) eval(s);                           // 若此时的遍历到的是一个运算符则调用上面的eval函数进行运算 
            else st.push(stoi(s));                            // 若为一个数字直接进栈
        }     
        return st.top();                                      // 遍历结束后返回栈顶元素即为后缀表达式的运算结果.  
    }
};

接下来看一道由中缀表达式进行求值的题目， 题目链接 : 3302. 表达式求值

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
给定一个表达式，其中运算符仅包含 +,-,*,/（加 减 乘 整除），可能包含括号，请你求出表达式的最终值。

注意：

数据保证给定的表达式合法。

题目保证符号 - 只作为减号出现，不会作为负号出现，例如，-1+2,(2+2)*(-(1+1)+2) 之类表达式均不会出现。题目保证表达式中所有数字均为正整数。题目保证表达式在中间计算过程以及结果中，均不超过 231−1。题目中的整除是指向 0 取整，也就是说对于大于 0 的结果向下取整，例如 5/3=1，对于小于 0 的结果向上取整，例如 5/(1−4)=−1。C++和Java中的整除默认是向零取整；Python中的整除//默认向下取整，因此Python的eval()函数中的整除也是向下取整，在本题中不能直接使用。

输入格式
共一行，为给定表达式。

输出格式
共一行，为表达式的结果。

数据范围
表达式的长度不超过 105。

输入样例：
(2+2)*(1+1)
输出样例：
8

这里给我们的是我们平常见到的表达式形式，这也叫中缀表达式, 我们如果对上面的表达式树进行中序遍历的话得到的结果为 2 + 2 * 1 + 1 , 看起来不太对劲，因为乘法优先级是大于加法，故还要加上括号，故这就是中缀表达式相比后缀麻烦的地方，需要处理输入的括号。 这里对于中缀表达式的求值，分两种思路;

1 将中缀转化为后缀表达式，然后利用上一道题的方法求值

这样的话其实相当于做两道题了，先转后缀再求表达式，显然麻烦，但通过上道题发现后缀求值确实容易，少了括号优先级的判断。

2 找出规律直接利用给出的中缀表达式求值

方法1： 中缀转后缀 –> 后缀再求值

#include<iostream>
#include<unordered_map>
#include<vector>
#include<algorithm>
#include<unordered_set>
#include<stack>
using namespace std;
vector<string> vstr;                       // 保存转化后的后缀表达式
/*********************中缀表达式转后缀表达式********************************/
/*
 * 转化规则: 
 * 从左到右遍历字符串,遇到数字直接加入vstr
 * 遇到左括号进栈     (优先级:左括号<加减运算符<乘除运算符)
 * 遇到运算符号,若栈顶符号的优先级较低,则该符号进栈,若栈顶优先级不低于当前符号,则将栈顶符号弹出到vstr中, 再次比较栈顶和新符号优先级....循环比较，直到当前符号的优先级大于栈顶符号的优先级
 * 遇到右括号,将栈顶符号依次弹出并加入vstr中, 直到碰到匹配的左括号
 * 遍历结束之后:将栈顶所有的符号弹出加入vstr中
 */

 //根据上面的转化规则进行转化
 auto convert(string &s)          // s为中缀表达式的字符串, convert函数将其转化为后缀表达式存放在vstr中
 {
     stack<string>st;
     unordered_map<string, int> priority = {{"(",0},{"+", 1}, {"-", 1}, {"*", 2}, {"/", 2}};    // 同上一道题
     for(int i = 0; i < s.size(); ++i)
     {
         string str;
         if(isdigit(s[i]))
         {
            while(i < s.size() && isdigit(s[i])) str += s[i++];
            vstr.push_back(str);
            if(i == s.size()) break;
         }

         if(s[i] == '(') st.push("(");
         else if(s[i] == ')')
         {
            while(st.size())
            {
                auto item = st.top(); st.pop();
                if(item == "(" ) break;
                else vstr.push_back(item);
            }
         }
         else
         {
             int s_pr;                                      // 判断当前字符的优先级
             if(s[i] == '-' || s[i] == '+')  s_pr = 1;
             else s_pr = 2;   
             while(st.size())
             {
                auto item = st.top();
                if(priority[item] >= s_pr) vstr.push_back(item), st.pop();
                else break;
             }
             st.emplace(1,s[i]);
         }
     }
     while(st.size())
     {
         auto item = st.top(); st.pop();
         vstr.push_back(item);
     }
 }

 auto bolan()      // 对我们的后缀表达式进行求值
 {
     stack<int> st;
     unordered_set<string> op = {"+", "-", "*", "/"};
     for(auto s : vstr)
     {
         if(!op.count(s)) st.push(stoi(s));
         else
         {
            int op2 = st.top(); st.pop(); 
            int op1 = st.top(); st.pop();
            if(s == "+") st.push(op1 + op2);
            else if(s == "-") st.push(op1 - op2);
            else if(s == "*") st.push(op1 * op2);
            else st.push(op1 / op2);
         }
     }
    return st.top();
 }

auto main() -> int
{
    string s; cin >> s;
    convert(s);
    cout << bolan() << endl;
    return 0;
}

#if 0
很明显代码很长， 先把中缀处理成后缀表达式，然后再进行求值，接下来介绍直接不进行转换就得到的方法
#endif

首先介绍一个简单的例子 ， a * b + c; 这个表达式的表达式树如下图，

对其进行中序遍历的结果如右图所示， 观察其遍历的顺序过程，对于中序遍历，只有两种情况，向下遍历或者向上遍历， 我们发现进行节点向上一层遍历遇到的都是运算符， 但是此时中序遍历遇到运算符并不能直接将此时局部给计算出来，因为此时遇到运算符时，其左子树说明已经遍历完毕，但还没遍历其右子树，故此时我们需要将这个运算符压栈，当我们下次再遇到一个运算符时，且此时运算符的符号小于栈顶的，即说明栈顶的运算符优先级更高，应该先完成运算，结合上图的例子就是, 我们遍历 a –> , 遇到乘号 * 时并不能完成运算，因为此时b还没遍历，故此时这个 * 先进行压栈， 然后我们继续遍历 b ，然后遍历完b后向上遍历遇到了 + , 此时其优先级小于我们栈顶的 , 同样由于遇到了运算符说明其左子树部分已经遍历完毕了，故这时把符号的栈顶弹出，数据的栈也弹出两个数进行运算。然后将运算结果压回数据栈中， 然后此时再比较此时运算符号栈中的栈顶是否还有其他元素或者栈顶依然大于当前遍历的运算符, 继续重复操作。 那如何处理括号呢? 这里的话左括号直接就是进符号栈, 当遇到右括号时，说明此时的之前的运算符要进行先运算了，故符号栈出栈并运算，直到遇到左括号为止。 故代码实现为:

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<stack>
#include<unordered_map>
using namespace std;
// 这里我们有两个栈，一个是数据栈，一个是符号栈 
stack<int> num;
stack<char> op;

// 弹出符号栈的一个符号和弹出数据栈的两个操作数进行求值，并将结果压栈
auto eval()
{
    int n2 = num.top(); num.pop();
    int n1 = num.top(); num.pop();
    auto c = op.top(); op.pop();
    if(c == '+') num.push(n1 + n2);
    else if(c == '-') num.push(n1 - n2);
    else if(c == '*') num.push(n1 * n2);
    else num.push(n1 / n2);
}

auto main(int argc, char *argv[]) -> int
{
    // 判断运算符的优先级 
    unordered_map<char, int> priority = {{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}, {'(', 0}};     
    string str; cin >> str;
    for(int i = 0; i < str.size(); ++i)
    {
        if(isdigit(str[i]))
        {
            int x = 0;
            while(i < str.size() && isdigit(str[i])) x = x * 10 + str[i++] - '0';
            num.push(x);                        // 数据进入数据栈
            if(i == str.size()) break;
        }

        if(str[i] == '(') op.push(str[i]);      // 遇到左括号直接进符号栈
        else if(str[i] == ')')                      
        {                                        
            while(op.top() != '(') eval();     // 遇到右括号，对符号栈出栈并运算.直到遇到左括号
            op.pop();       
        }
        else
        {
            while(op.size() && priority[op.top()] >= priority[str[i]]) eval();   // 遇到运算符,判断其优先级与符号栈的优先级, 一般来说先进栈的优先级比较高, 若栈顶优先级大于当前符号，说明其前面的要先运算出结果，直到当前符号优先级大于栈顶 
            op.push(str[i]);       // 然后将当前符号进栈
        }
    }
    while(op.size()) eval();
    cout << num.top() << endl;
    return 0;
}