C++实现逆波兰表达式的例题详解

目录
  • 1. 题目描述
  • 2. 解题思路
  • 3. 动图演示
  • 4. 代码实现

1. 题目描述

2. 解题思路

逆波兰表达式由波兰的逻辑学家卢卡西维兹提出，它的特点是：没有括号，运算符总是放在和它相关的操作数之后。因此，逆波兰表达式也称后缀表达式，它严格遵循「从左到右」的运算。

在我们平时生活中，使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 )。

该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

计算逆波兰表达式的值时，使用一个栈存储操作数，从左到右遍历逆波兰表达式，进行如下操作：

  • 从左至右扫描该算术表达式，从第一个字符开始判断，如果该字符是数字，则将数字入栈；
  • 如果不是数字，该字符则是运算符，如果遇到运算符，则将栈里面的两个操作数出栈，其中先出栈的是右操作数，后出栈的是左操作数， 使用运算符对两个操作数进行运算，将运算得到的新操作数入栈。

整个逆波兰表达式遍历完毕之后，栈内只有一个元素，该元素即为逆波兰表达式的值。

3. 动图演示

来看个动图

4. 代码实现

有一点需要注意，num 1 和 num2 进行运算的时候，num1 是右操作数，num2 是左操作数，别写反了！！！

代码示例

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<long long> st;
        for (auto& str : tokens) {
            if (str == "+" || str == "-" || str == "*" || str == "/") {
                auto num1 = st.top();
                st.pop();
                auto num2 = st.top();
                st.pop();

                if (str == "+") {
                    st.push(num2 + num1);
                }
                else if (str == "-") {
                    st.push(num2 - num1);
                }
                else if (str == "*") {
                    st.push(num2 * num1);
                }
                else if (str == "/") {
                    st.push(num2 / num1);
                }
            }
            else {
                st.push(stoi(str)); // 如果是操作数就入栈，因为这是字符，所以要转成数字
            }
        }
        return st.top();
    }
};

到此这篇关于C++实现逆波兰表达式的例题详解的文章就介绍到这了,更多相关C++逆波兰表达式内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C++实现LeetCode(150.计算逆波兰表达式)

    [LeetCode] 150.Evaluate Reverse Polish Notation 计算逆波兰表达式 Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid operators are +, -, *, /. Each operand may be an integer or another expression. Note: Division between two integ

  • C++实现逆波兰式

    (a+b)c的逆波兰式为ab+c,假设计算机把ab+c按从左到右的顺序压入栈中,并且按照遇到运算符就把栈顶两个元素出栈,执行运算,得到的结果再入栈的原则来进行处理,那么ab+c的执行结果如下: 1)a入栈(0位置) 2)b入栈(1位置) 3)遇到运算符"+",将a和b出栈,执行a+b的操作,得到结果d=a+b,再将d入栈(0位置) 4)c入栈(1位置) 5)遇到运算符"",将d和c出栈,执行dc的操作,得到结果e,再将e入栈(0位置) 经过以上运算,计算机就可以得到

  • C++栈实现逆波兰式的应用

    C++栈实现逆波兰式的应用

    目录 一.定义 二.逆波兰式的意义 三.逆波兰式的实现 1.方法 2.代码实现 一.定义 逆波兰式,又称后缀表达式,指的是操作符在其所控制的操作数后面的表达式. 举个例子,1 + 2 * 3 - 4这个表达式是我们熟悉的中缀表达式,那么其所对应的后缀表达式为:1 2 3 * + 4 -. 再来个复杂的例子:1 * (2 + 3) / 5 - 4 / 2其对应的后缀表达式为:1 2 3 + * 5 / 4 2 / -(其中括号由于只是提升表达式优先级的作用,因此不放入后缀表达式中). 二.逆波兰式

  • C++代码实现逆波兰表达式

    本文实例为大家分享了C++实现逆波兰表达式的具体代码,供大家参考,具体内容如下 当我们输入一个数学表达式,是中缀表达式,我们首先转换为后缀表达式(逆波兰表达式),然后再进行求值. 在<大话数据结构>的104-100页有详细的介绍,下面是我理解之后的代码实现. 代码思路: (1)首先对输入的中缀表达式合法性进行判断,bool isStringLegal(const char* str); 函数实现. (2)然后把中缀表达式转换为后缀表达式. (3)根据后缀表达式求出结果,double getTh

  • C++代码实现逆波兰式

    100行以内C++代码实现逆波兰式 逆波兰式(Reverse Polish notation,RPN,或逆波兰记法),也叫后缀表达式(将运算符写在操作数之后). 算术表达式转逆波兰式例子: 逆波兰式整体的算法流程图如下: 下面给出我基于C++ 语言对逆波兰式算法的实现代码,值得注意的是: 1.算法中对操作数,仅支持一个字符的字母或数字的操作数,如:x,y,j,k,3,7等:如果要支持多个字符的操作数,如:var1,3.14等.需要读者自己扩展对算术表达式操作数的分词部分的代码. 2.为了为了增加

  • C++实现逆波兰表达式的例题详解

    目录 1. 题目描述 2. 解题思路 3. 动图演示 4. 代码实现 1. 题目描述 2. 解题思路 逆波兰表达式由波兰的逻辑学家卢卡西维兹提出,它的特点是:没有括号,运算符总是放在和它相关的操作数之后.因此,逆波兰表达式也称后缀表达式,它严格遵循「从左到右」的运算. 在我们平时生活中,使用的算式则是一种中缀表达式,如 ( 1 + 2 ) * ( 3 + 4 ). 该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) . 计算逆波兰表达式的值时,使用一个栈存储操作数,从

  • Java编程实现逆波兰表达式代码示例

    逆波兰表达式 定义:传统的四则运算被称作是中缀表达式,即运算符实在两个运算对象之间的.逆波兰表达式被称作是后缀表达式,表达式实在运算对象的后面. 逆波兰表达式: a+b ---> a,b,+ a+(b-c) ---> a,b,c,-,+ a+(b-c)*d ---> a,b,c,-,d,*,+ a+d*(b-c)--->a,d,b,c,-,*,+ a=1+3 ---> a=1,3 + http=(smtp+http+telnet)/1024 写成什么呢? http=smtp,

  • Python实现处理逆波兰表达式示例

    本文实例讲述了Python实现处理逆波兰表达式.分享给大家供大家参考,具体如下: 中文名: 逆波兰表达式 外文名: Reverse Polish Notation 别名: 后缀表达式 逆波兰表达式又叫做后缀表达式.在通常的表达式中,二元运算符总是置于与之相关的两个运算对象之间,这种表示法也称为中缀表示.波兰逻辑学家J.Lukasiewicz于1929年提出了另一种表示表达式的方法,按此方法,每一运算符都置于其运算对象之后,故称为后缀表示.这个知识点在数据结构和编译原理这两门课程中都有介绍.它的优

  • Java实现简易计算器(逆波兰表达式)

    Java实现简易计算器(逆波兰表达式)

    本文实例为大家分享了Java实现简易计算器的具体代码,供大家参考,具体内容如下 程序的运行环境为Windows10 ,编译环境为IDEA. 计算器有以下功能和要求:能够计算复杂表达式,实现对多位数和负数以及小数的多则复杂计算 已完善功能(Bug): 1,能够计算大数字,小数,负数 2,小数点,运算符等不能连续输入(例如 ..,++,**等) 3,小数点前没有数字时自动补0并在输入框显示“0.”若小数点前是数字,且前面的数字串里含有".",则不能继续输入小数点(“.”---”0.“ ,1

  • JSP中EL表达式的用法详解(必看篇)

    EL 全名为Expression Language EL 语法很简单,它最大的特点就是使用上很方便.接下来介绍EL主要的语法结构: ${sessionScope.user.sex} 所有EL都是以${为起始.以}为结尾的.上述EL范例的意思是:从Session的范围中,取得 用户的性别.假若依照之前JSP Scriptlet的写法如下: User user =(User)session.getAttribute("user"); String sex =user.getSex( );

  • JSP中表达式的使用详解

    JSP表达式用于向页面中输出信息,其语法格式如下: <%= 表达式 %> 参数说明: 表达式:可以是任何Java语音的完整表达式.该表达式的最终运算结果将被转换为字符串. 下面举一些简单示例演示: <%@ page language="java" import="java.util.*" contentType="text/html; charset=UTF-8" pageEncoding="UTF-8"%&

  • Spring 整合Shiro 并扩展使用EL表达式的实例详解

    Shiro是一个轻量级的权限控制框架,应用非常广泛.本文的重点是介绍Spring整合Shiro,并通过扩展使用Spring的EL表达式,使@RequiresRoles等支持动态的参数.对Shiro的介绍则不在本文的讨论范围之内,读者如果有对shiro不是很了解的,可以通过其官方网站了解相应的信息.infoq上也有一篇文章对shiro介绍比较全面的,也是官方推荐的,其地址是https://www.infoq.com/articles/apache-shiro. Shiro整合Spring 首先需要

  • python if三元表达式实例用法详解

    1.说明 使用一行代码快速判断,更换复杂的多行if语句,使代码能够简单地维护. if三元表达式的阅读方式有点不符合阅读习惯.从句子中间的if条件开始读,条件满足的话,得到左侧的值x,条件不满足的话,得到else下面的值x. 2.实例 result = x if x > 0 else -x >>> x = -15 >>> x if x > 0 else -x 15 知识点扩展: public class java { public static void ma

随机推荐