C++题解 | 逆波兰表达式相关网站首页 技术教程

C++题解 | 逆波兰表达式相关

夜默 2023-04-27 22:30:02

简介C++题解 | 逆波兰表达式相关

✨个人主页： 夜默
🎉所属专栏： C/C++相关题解
🎊每篇一句： 图片来源

A year from now you may wish you had started today.
明年今日，你会希望此时此刻的自己已经开始行动了。

文章目录

🌇前言
🏙️正文
🌆总结

🌇前言

好久没有更新题解系列博客了，今天要学习的是 逆波兰表达式，作为计算机中的重要概念，值得花时间去学习，并且其中还必须使用 容器适配器，非常适合用来练手

逆波兰表达式

🏙️正文

1、什么是逆波兰表达式？

逆波兰表达式 又称为 后缀表达式，我们从小到大学习的数学相关运算式都是 前缀表达式

前缀表达式：运算符在操作数中间 (a + b) * c
后缀表达式：运算符在操作数后面 a b + c *

为什么会存在这种反人类的表达式呢？

因为运算式中，可能存在 ( ) 提高运算优先级的现象，计算机不像人类一样，可以一眼找到 ( ) 进行运算，只能通过特殊方法，处理运算式，使其能进行正常运算

因此，后缀表达式中是没有括号的

操作数：a、b、c
运算符：+、*

后缀表达式 的计算步骤：

从左往右，扫描表达式
获取 操作数1 与 操作数2
再获取 运算符
进行运算：操作数1 运算符操作数2，获取运算结果
将运算结果继续与后续 操作数、运算符 进行计算

比如计算 12+3*

首先计算 1 + 2 = 3
其次再计算 3 * 3 = 9

最后的 9 就是最终运算结果，逆波兰表达式（后缀表达式）有效解决了计算时的优先级问题

了解 逆波兰表达式 基础知识后，就可以尝试解决相关问题了~

2、150. 逆波兰表达式求值 ⭐⭐

首先来看看第一题，也是比较简单的一题：150.逆波兰表达式求值

题目链接：150.逆波兰表达式求值

题目要求：根据 逆波兰表达式 计算出结果

这里可以直接根据 逆波兰表达式（后缀表达式） 的计算步骤进行解题

解题思路：

从左往右扫描表达式（遍历即可）
遇到操作数（数字），入栈
遇到运算符，取出栈中的两个两个操作数，进行计算
将计算结果重新入栈
如此重复，直到表达式被扫描完毕

所需要的辅助工具：栈 stack
复杂度分析：

时间复杂度 O(N) 遍历一遍表达式 + 出栈入栈
空间复杂度 O(N) 需要使用大小足够的栈

转化为代码是这样的：

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        //首先需要一个栈，用来存储操作数
        stack<int> numStack;

        //对表达式进行遍历
        for (size_t pos = 0; pos != tokens.size(); pos++)
        {
            //判断是否为操作数
            //需要注意负数,负数大小是大于1的
            if (isdigit(tokens[pos][0]) || tokens[pos].size() > 1)
            {
                //满足条件，入栈
                //注意：入栈的是整型！
                numStack.push(stoi(tokens[pos]));
            }
            else
            {
                //此时为运算符，需要进行运算
                //注意：先取的是右操作数
                int rightNum = numStack.top();
                numStack.pop();
                int leftNum = numStack.top();
                numStack.pop();

                char oper = tokens[pos][0];   //运算符
                int val = 0;    //运算结果
                switch (oper)
                {
                case '+':
                    val = leftNum + rightNum;
                    break;
                case '-':
                    val = leftNum - rightNum;
                    break;
                case '*':
                    val = leftNum * rightNum;
                    break;
                case '/':
                    val = leftNum / rightNum;
                    break;
                default:
                    break;
                }

                //将运算结果入栈
                numStack.push(val);
            }
        }

        //此时栈中的元素，就是计算结果
        return numStack.top();
    }
};

运行结果：

需要注意的点：

isdigit 函数可以判断字符是否数字字符
判断是否为操作数时，需要注意负数的情况，如 -100，可以通过判断字符串大小解决（运算符大小只为1）
操作数入栈时，入的是整型，而非字符串，可以使用 stoi 函数进行转换
取操作数时，先取到的是右操作数，-、/ 这两个运算符需要注意运算顺序
获得运算结果后，需要再次入栈

3、224. 基本计算器 ⭐⭐⭐

直接利用 后缀表达式 计算出结果很简单，但将 中缀表达式 转为 后缀表达式 就比较麻烦了

在力扣中就存在这样一道 困难题

题目链接：基本计算器

题目要求：根据 中缀表达式，计算出结果

注意： 给出的 中缀表达式 中只涉及 +、- 运算，但是其中又会存在很多特殊情况

为了使得这些特殊情况统一化，在进行表达式转换前，需要先去除其中的空格，这样就能以较为统一的视角解决问题

解题思路：

去除 中缀表达式 中的空格，方便后续进行转换
获取 逆波兰表达式（后缀表达式） （重难点）
根据 逆波兰表达式 求出结果即可

如何将 中缀表达式 转换为 后缀表达式 ?

操作数输出（非打印，而是尾插至 vector 中）
运算符：如果栈为空，直接入栈；如果栈不为空，与栈顶运算符进行优先级比较，如果比栈顶运算符优先级高，入栈，否则将栈顶运算符弹出（输出），继续比较
对于 ()，认为它们的优先级都为最低，并且 ( 直接入栈，而 ) 直接弹出栈顶元素，直到遇见 (
最后将栈中的运算符全部弹出

注意： 对于可能存在的负数，需要进行特别处理

当 - 单独出现时（左右都没有操作数），表示此时需要将右边括号中的计算结果 * -1，此时可以直接先输出元素 0，后续进行 0 - val 时，可以满足需求
当 - 仅有右边有操作数时，此时为一个单独出现的负数，输出此负数即可
当 - 左右都有操作数时，此时的 - 就是一个单纯的运算符

class Solution {
public:
    //去除空格
    int spaceRemove(string& s)
    {
        int begin = 0;
        int end = 0;
        int alphaNum = 0;
        while (end != s.size())
        {
            if (s[end] != ' ')
            {
                if (s[end] != '(' && s[end] != ')')
                    alphaNum++;
                s[begin] = s[end];
                begin++;
                end++;
            }
            else
                end++;
        }
        s.resize(begin);

        return alphaNum;
    }

    //判断是否为负数
    bool isNega(const string& s, int i)
    {
        //合法的负数：左边为 '(' 或者 左边为空
        return s[i] == '-' && (i == 0 || s[i - 1] == '(');
    }

    //获取逆波兰表达式
    void getAntiPoland(vector<string>& tokens, string s)
    {
        //借助栈，存储运算符
        stack<char> oper;

        size_t i = 0;
        while (i < s.size())
        {
            string str;

            //操作数直接输出
            if (isdigit(s[i]) || isNega(s, i))
            {
                //有可能为负数
                if (s[i] == '-')
                {
                    //特殊情况，'-' 单独出现，不配合数字
                    if (i + 1 < s.size() && !isdigit(s[i + 1]))
                    {
                        str += '0';
                        oper.push(s[i++]);
                    }
                    //普通负数的情况
                    else
                    {
                        str += s[i];
                        i++;
                    }
                }

                //处理多位数的情况
                while (isdigit(s[i]))
                {
                    str += s[i];
                    i++;
                }
            }
            else
            {
                //此时为运算符
                //栈空 或者 '(' 直接入栈
                if (oper.empty() || s[i] == '(')
                    oper.push(s[i]);
                else
                {
                    if (s[i] == ')')
                    {
                        //此时需要不断弹出
                        char tmp = oper.top();
                        oper.pop();
                        while (tmp != '(')
                        {
                            str += tmp;
                            tmp = oper.top();
                            oper.pop();
                        }
                    }
                    else if (oper.top() != '(')
                    {
                        //此时弹出并入栈
                        str = oper.top();
                        oper.pop();
                        oper.push(s[i]);
                    }
                    else
                    {
                        //此时该运算符的优先级比前面的高，直接入栈
                        oper.push(s[i]);
                    }
                }
                i++;
            }

            if (!str.empty())
                tokens.push_back(str);  //计入中缀表达式
        }

        //最后需要将栈中的运算符全部弹出
        string str;
        while (!oper.empty())
        {
            str += oper.top();
            oper.pop();
        }
        if (!str.empty())
            tokens.push_back(str);
    }

    int evalRPN(vector<string>& tokens) {
        //首先需要一个栈，用来存储操作数
        stack<int> numStack;

        //对表达式进行遍历
        for (size_t pos = 0; pos != tokens.size(); pos++)
        {
            //判断是否为操作数
            //需要注意负数,负数大小是大于1的
            if (isdigit(tokens[pos][0]) || tokens[pos].size() > 1)
            {
                //满足条件，入栈
                //注意：入栈的是整型！
                numStack.push(stoi(tokens[pos]));
            }
            else
            {
                //此时为运算符，需要进行运算
                //注意：先取的是右操作数
                int rightNum = numStack.top();
                numStack.pop();
                int leftNum = numStack.top();
                numStack.pop();

                char oper = tokens[pos][0];   //运算符
                int val = 0;    //运算结果
                switch (oper)
                {
                case '+':
                    val = leftNum + rightNum;
                    break;
                case '-':
                    val = leftNum - rightNum;
                    break;
                default:
                    break;
                }

                //将运算结果入栈
                numStack.push(val);
            }
        }

        //此时栈中的元素，就是计算结果
        return numStack.top();
    }
    int calculate(string s) {
        //核心：运算符入栈，操作数输出，根据运算符优先级进行弹出
        int alphaNum = spaceRemove(s); //为了方便后续操作，可以先去除空格
        vector<string> tokens;  //存储操作数+运算符的后缀表达式
        tokens.reserve(alphaNum);	//提前扩容，避免造成浪费
        getAntiPoland(tokens, s);   //获取逆波兰表达式（后缀表达式）
        int val = evalRPN(tokens);  //复用之前写的代码
        return val;
    }
};