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

这篇具有很好参考价值的文章主要介绍了C++题解 | 逆波兰表达式相关。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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

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

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



🌇前言

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

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


🏙️正文

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

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

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

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

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

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

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

后缀表达式 的计算步骤:

  1. 从左往右,扫描表达式
  2. 获取 操作数1操作数2
  3. 再获取 运算符
  4. 进行运算:操作数1 运算符 操作数2,获取运算结果
  5. 将运算结果继续与后续 操作数运算符 进行计算

比如计算 12+3*

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

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

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


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

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

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

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

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

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

解题思路:

  1. 从左往右扫描表达式(遍历即可)
  2. 遇到操作数(数字),入栈
  3. 遇到运算符,取出栈中的两个两个操作数,进行计算
  4. 将计算结果重新入栈
  5. 如此重复,直到表达式被扫描完毕

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

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

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

转化为代码是这样的:

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();
    }
};

运行结果:
C++题解 | 逆波兰表达式相关

需要注意的点:

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

2023.6.4 更新

//2023.6.4 更新
//利用包装器和lambda,使代码更加优雅

#include <map>
#include <functional>

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        //首先需要一个栈,用来存储操作数
        stack<int> numStack;
        map<string, function<int(int,int)>> table = 
        {
            {"+", [](int leftNum, int rightNum)->int{ return leftNum + rightNum;} },
            {"-", [](int leftNum, int rightNum)->int{ return leftNum - rightNum;} },
            {"*", [](int leftNum, int rightNum)->int{ return leftNum * rightNum;} },
            {"/", [](int leftNum, int rightNum)->int{ return leftNum / rightNum;} }
        };

        //对表达式进行遍历
        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();

                string oper = tokens[pos];   //运算符
                int val = table[oper](leftNum, rightNum);    //运算结果

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

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

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


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

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

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

题目链接:基本计算器

C++题解 | 逆波兰表达式相关
题目要求:根据 中缀表达式,计算出结果

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

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

解题思路:

  1. 去除 中缀表达式 中的空格,方便后续进行转换
  2. 获取 逆波兰表达式(后缀表达式) (重难点)
  3. 根据 逆波兰表达式 求出结果即可

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

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

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

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

  • - 单独出现时(左右都没有操作数),表示此时需要将右边括号中的计算结果 * -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;
    }
};

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

注:因为走的是先转换,再计算的步骤,所以整体性能会比较差,但其中加入了 逆波兰表达式 的相关知识,还是比较适合用来练手的


🌆总结

以上就是本次 逆波兰表达式 相关内容了,希望你在看完本文后能够有所收获

如果你觉得本文写的还不错的话,可以留下一个小小的赞👍,你的支持是我分享的最大动力!

如果本文有不足或错误的地方,随时欢迎指出,我会在第一时间改正


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

文章来源地址https://www.toymoban.com/news/detail-430576.html

相关文章推荐

C语言题解 | 去重数组&&合并数组

C语言题解 | 消失的数字&轮转数组

C语言题解——除自身以外数组的乘积(力扣 第238题)

剑指Offer 第53题:数字在升序数组中出现的次数

C语言题解——倒置字符串(剑指Offer 第58题)

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

到了这里,关于C++题解 | 逆波兰表达式相关的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 栈|逆波兰表达式求值

    逆波兰表达式求值 逆波兰表达式就是后缀表达式,我们平时写的带括号的是中缀表达式。区分中缀表达式和后缀表达式 就是 操作数 和 操作符 的先后关系。 操作符在后 就是后缀表达式 后缀表达式 的用途就是 让计算机直到计算的先后顺序! 比如 我们中缀表达式 a * (b -

    2024年04月11日
    浏览(47)
  • PTA: h0116. 波兰表达式

    (PTA题目描述有误,应该是波兰表达式)逆波兰表达式是一种把运算符前置的算术表达式,例如普通的表达式2 + 3的逆波兰表示法为+ 2 3。逆波兰表达式的优点是运算符之间不必有优先级关系,也不必用括号改变运算次序,例如(2 + 3) * 4的逆波兰表示法为* + 2 3 4。本题求解逆波

    2024年02月06日
    浏览(34)
  • LeetCode:150. 逆波兰表达式求值—栈

    🍎道阻且长,行则将至。🍓 🌻算法,不如说它是一种思考方式🍀 算法专栏: 👉🏻123 题目描述 :给你一个字符串数组 tokens ,表示一个根据 逆波兰表示法 表示的算术表达式。 请你计算该表达式。返回一个表示表达式值的整数。 来源:力扣(LeetCode) 难度: 简单 提示:

    2023年04月16日
    浏览(55)
  • 『力扣刷题本』:逆波兰表达式求值

    大家好久不昂,最近 1 个多月罗根一直在备考期末,文章发的很少。 现在已经放寒假啦,学习自然也不能拉下,毕竟 4 月份就要去参加蓝桥杯了。 先给自己定个小目标,日更 2 篇! 咳咳,下面马上开始讲题👇 给你一个字符串数组  tokens  ,表示一个根据 逆波兰表示法 表

    2024年01月16日
    浏览(38)
  • JAVA练习99-逆波兰表达式求值

    提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 目录 前言 一、题目-逆波兰表达式求值 1.题目描述 2.思路与代码 2.1 思路 2.2 代码 总结 提示:这里可以添加本文要记录的大概内容: 4月5日练习内容 提示:以下是本篇文章正文内容,下面案例可供参考

    2023年04月08日
    浏览(44)
  • 力扣:150. 逆波兰表达式求值(Python3)

    给你一个字符串数组  tokens  ,表示一个根据 逆波兰表示法 表示的算术表达式。 请你计算该表达式。返回一个表示表达式值的整数。 注意: 有效的算符为  \\\'+\\\' 、 \\\'-\\\' 、 \\\'*\\\'  和  \\\'/\\\'  。 每个操作数(运算对象)都可以是一个整数或者另一个表达式。 两个整数之间的除法总

    2024年02月05日
    浏览(53)
  • 【算法入门】 有效括号序列|逆波兰表达式求值|点击消除

    ✅作者简介:热爱后端语言的大学生,CSDN内容合伙人 ✨精品专栏:C++面向对象 🔥系列专栏:算法百炼成神 本专栏收录的均为牛客网的算法题目,内含链表、双指针、递归、动态规划、基本数据结构等算法思想的具体运用。牛客网不仅有大量的经典算法题目,也有大厂的面

    2024年02月12日
    浏览(41)
  • 262.【华为OD机试真题】符号运算(中缀表达式转逆波兰表达式-Java&Python&C++&JS实现)

    🚀点击这里可直接跳转到本专栏,可查阅顶置最新的华为OD机试宝典~ 本专栏所有题目均包含优质解题思路,高质量解题代码(JavaPythonC++JS分别实现),详细代码讲解,助你深入学习,深度掌握!

    2024年02月21日
    浏览(41)
  • 【LeetCode专题#基本计算器】基本计算器I,图解中序表达式转逆波兰表达式,太难了

    https://leetcode.cn/problems/basic-calculator/?envType=listenvId=cKNEfNsF 给你一个字符串表达式 s ,请你实现一个基本计算器来计算并返回它的值。 注意:不允许使用任何将字符串作为数学表达式计算的内置函数,比如 eval() 。 示例 1: 输入:s = \\\"1 + 1\\\" 输出:2 示例 2: 输入:s = \\\" 2-1 + 2 \\\" 输出

    2024年02月08日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包