中后缀表达式

一、利用后缀表达式进行计算

1)解题思路

  1. 如果当前字符串是操作数,就将该操作数入栈;
  2. 如果当前字符串是操作符,就取栈顶的两个操作数进行运算(注意:第一个出栈的数为计算时的右操作数;第二个出栈的数为计算是的左操作数),并将运算结果重新入栈;
  3. 重复上面两个步骤,直到字符串遍历完:最后栈里面的值就是计算结果。

2)代码

int evalRPN(vector<string>& tokens) 
    {
        stack<int> st;
        // 遍历字符
        for(auto& e : tokens)
        {
            // 如果遇到的是运算符,取出栈中的两个元素运算,并将运算结果入栈
            if(e == "+" || e == "-" || e == "*" || e == "/")
            {
                int num2 = st.top();
                st.pop();
                int num1 = st.top();
                st.pop(); 
                if(e == "+")
                    st.push(num1+num2);
                if(e == "-")
                    st.push(num1-num2);
                if(e == "*")
                    st.push(num1*num2);
                if(e == "/")
                    st.push(num1/num2);
            }
            // 如果是操作数,如入栈
            else
            {
                st.push(stoi(e));
            }
        } 
        return st.top();
    }
};

3)注意点

如果当前字符串为操作数时,需要先使用 stoi() 函数将字符串转化为数字后,将其入栈。

题目链接:

150. 逆波兰表达式求值 - 力扣(LeetCode)

二、中缀表达式转后缀表达式

1)解题思路

  1. 如果当前字符为操作数,直接输出;
  2. 如果当前字符为操作符,判断当前栈是否为空:
    1. 如果栈为空,将该操作符入栈;
    2. 如果栈不为空,将该操作符与栈顶元素比较优先级:
      1. 如果当前操作符优先级高,入栈;
      2. 如果当前操作符优先级相等或较低,输出栈顶元素。

还需要考虑,括号带来的优先级问题:不能仅仅根据运算符本身的优先级进行比较。

这里有好几种处理方法,在这里我介绍一种:

  1. 遇到 ( 时,将它入栈,并且认为它的优先级是最低的,这样才能保证括号内部的操作符才能入栈;
  2. 同时遇到 ) 时,我们还是认为它的优先级是最低的,这样才能保证括号内部的操作符能够出栈进行计算,并且出栈 - 后,并且遇到( 后,将其出栈。
  3. 最后如果栈空也不进行入栈操作,并进行下一个操作的判断。

括号的特殊处理,总结一下:

  1. ()的优先级最低;
  2. ( 不进行优先级的比较,直接入栈;
  3. ) 进行比较,输出栈顶元素,直到遇到( 。

下面举个例子,模拟一个这个过程:

当将中缀表达式1+2*(4-5*2)+6/7转化为后缀表达式时,可以按照以下步骤进行:

  1. 创建一个空栈和一个空列表(用于存放后缀表达式)。

  2. 从左到右遍历中缀表达式中的每个元素,按照以下规则处理:

    • 遇到数字时,直接加入到后缀表达式列表中。

    • 遇到运算符时,分两种情况:

      • 如果栈为空或者栈顶元素为左括号,将当前运算符压入栈中。
      • 否则,如果当前运算符的优先级小于等于栈顶运算符的优先级,则将栈顶运算符弹出并加入到后缀表达式列表中,直到栈顶运算符的优先级小于当前运算符的优先级或者栈为空,然后将当前运算符压入栈中。
    • 遇到左括号时,将其压入栈中。

    • 遇到右括号时,依次弹出栈顶元素并加入到后缀表达式列表中,直到遇到左括号为止。注意:左右括号不应该加入到后缀表达式列表中。

  3. 如果中缀表达式已经遍历完毕,则将栈中剩余的运算符依次弹出并加入到后缀表达式列表中。

  4. 后缀表达式列表即为转换得到的后缀表达式。

以下是将中缀表达式1+2*(4-5*2)+6/7转化为后缀表达式的详细过程:

  1. 初始化栈和后缀表达式列表为空。

  2. 从左到右遍历中缀表达式:

    • 遇到字符'1',加入后缀表达式列表:['1']
    • 遇到字符'+',将其压入栈中:栈:['+']
    • 遇到字符'2',加入后缀表达式列表:['1', '2']
    • 遇到字符'*',将其压入栈中:栈:['+', '*']
    • 遇到字符'(',将其压入栈中:栈:['+', '*', '(']
    • 遇到字符'4',加入后缀表达式列表:['1', '2', '4']
    • 遇到字符'-',将其压入栈中:栈:['+', '*', '(', '-']
    • 遇到字符'5',加入后缀表达式列表:['1', '2', '4', '5']
    • 遇到字符'*',将其压入栈中:栈:['+', '*', '(', '-', '*']
    • 遇到字符'2',加入后缀表达式列表:['1', '2', '4', '5', '2']
    • 遇到字符')',弹出栈顶元素并加入后缀表达式列表,直到遇到左括号为止:['1', '2', '4', '5', '2', '*', '-']
    • 弹出左括号'('。
    • 遇到字符'+',将其压入栈中:栈:['+', '+']
    • 遇到字符'6',加入后缀表达式列表:['1', '2', '4', '5', '2', '*', '-', '6']
    • 遇到字符'/',将其压入栈中:栈:['+', '+', '/']
    • 遇到字符'7',加入后缀表达式列表:['1', '2', '4', '5', '2', '*', '-', '6', '7']
  3. 中缀表达式已经遍历完毕,将栈中剩余的运算符依次弹出并加入到后缀表达式列表中:['1', '2', '4', '5', '2', '*', '-', '6', '7', '/', '+', '+']

  4. 后缀表达式为1 2 4 5 2 * - * + 6 7 / +

这就是将中缀表达式1+2*(4-5*2)+6/7转化为后缀表达式的详细过程。

2)代码

#include <iostream>
#include <stack>
#include <string>
#include <vector>

bool isOperator(char ch) {
    return (ch == '+' || ch == '-' || ch == '*' || ch == '/');
}

int getPriority(char op) {
    if (op == '+' || op == '-')
        return 1;
    else if (op == '*' || op == '/')
        return 2;
    return 0;
}

std::vector<std::string> infixToPostfix(const std::string& infix) {
    std::vector<std::string> postfix;
    std::stack<char> opStack;

    for (unsigned i = 0; i < infix.length(); ++i) {
        char ch = infix[i];

        if (ch == ' ') {
            continue;
        }
        else if (isdigit(ch)) {
            std::string num;
            while (i < infix.length() && (isdigit(infix[i]) || infix[i] == '.')) {
                num += infix[i++];
            }
            --i;
            postfix.push_back(num);
        }
        else if (isOperator(ch)) {
            while (!opStack.empty() && opStack.top() != '(' &&
                   getPriority(opStack.top()) >= getPriority(ch)) {
                postfix.push_back(std::string(1, opStack.top()));
                opStack.pop();
            }
            opStack.push(ch);
        }
        else if (ch == '(') {
            opStack.push(ch);
        }
        else if (ch == ')') {
            while (!opStack.empty() && opStack.top() != '(') {
                postfix.push_back(std::string(1, opStack.top()));
                opStack.pop();
            }
            opStack.pop(); // Discard '('
        }
    }

    while (!opStack.empty()) {
        postfix.push_back(std::string(1, opStack.top()));
        opStack.pop();
    }

    return postfix;
}

int main() {
    std::string infixExpression = "1+2*(4-5*2)+6/7";
    std::vector<std::string> postfixExpression;

    postfixExpression = infixToPostfix(infixExpression);

    for (const auto& token : postfixExpression) {
        std::cout << token << " ";
    }
    std::cout << std::endl;

    return 0;
}

遇到 ( 时,将它入栈,并且认为它的优先级是最低的,这样才能保证括号内部的操作符才能入栈;

同时遇到 ) 时,我们还是认为它的优先级是最低的,这样才能保证括号内部的操作符能够出栈进行计算,并且出栈 - 后,并且遇到( 后,将其出栈,最后如果栈空也不进行入栈操作,并进行下一个操作的判断。

同时也可以使用增加一个flag标签的方法:

我们可以将这个flag初始化为0,只有遇到( 时,将flag = 1,通过flag的值判断下一个操作符的优先级,当flag = 1时,无论下一个操作符是什么,我们都认为它的优先级是高于此时栈顶操作符的,并进行入栈操作。当遇到)时,将flag置为0;

也可以使用递归,将()内部的表达式用一个新的栈进行计算,并将结果返回。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/271294.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

继电器负载的使用方法有哪些?

继电器是通过电磁效应或电热效应实现电路的自动开关。继电器负载是指继电器所控制的负载&#xff0c;通常包括电机、灯泡、加热器等。正确使用继电器负载可以确保设备的正常运行和安全。以下是一些使用继电器负载的方法&#xff1a; 选择合适的继电器&#xff1a;根据负载的类型…

基于java+控件台+mysql的学生信息管理系统(含演示视频)

基于java控件台mysql的学生信息管理系统_含演示视频 一、系统介绍二、功能展示1.项目内容2.项目骨架3.数据库4.登录系统5.新增学生6.查询学生7.修改学生8.删除学生9.退出系统 四、其它1.其他系统实现五.获取源码 一、系统介绍 项目类型&#xff1a;Java SE项目&#xff08;控制…

大数据开发之Sqoop详细介绍

测试环境 CDH 6.3.1 Sqoop 1.4.7 一.Sqoop概述 Apache Sqoop&#xff08;SQL-to-Hadoop&#xff09;项目旨在协助RDBMS与Hadoop之间进行高效的大数据交流。用户可以在 Sqoop 的帮助下&#xff0c;轻松地把关系型数据库的数据导入到 Hadoop 与其相关的系统 (如HBase和Hive)中&…

Java经典框架之Spring MVC

Spring MVC Java 是第一大编程语言和开发平台。它有助于企业降低成本、缩短开发周期、推动创新以及改善应用服务。如今全球有数百万开发人员运行着超过 51 亿个 Java 虚拟机&#xff0c;Java 仍是企业和开发人员的首选开发平台。 课程内容的介绍 1. Spring MVC 入门案例 2. 基…

Github 2023-12-23 开源项目日报 Top10

根据Github Trendings的统计&#xff0c;今日(2023-12-23统计)共有10个项目上榜。根据开发语言中项目的数量&#xff0c;汇总情况如下&#xff1a; 开发语言项目数量Python项目6C项目2C项目1Jupyter Notebook项目1HTML项目1Go项目1非开发语言项目1 免费API集体清单 创建周期…

【中小型企业网络实战案例 二】配置网络互连互通

​【中小型企业网络实战案例 一】规划、需求和基本配置-CSDN博客 热门IT技术视频教程&#xff1a;https://xmws-it.blog.csdn.net/article/details/134398330?spm1001.2014.3001.5502 配置接入层交换机 1.以接入交换机ACC1为例&#xff0c;创建ACC1的业务VLAN 10和20。 <…

哪些超声波清洗机值得买?五款超声波清洗机实测大对比!

在当今快节奏的生活中&#xff0c;我们对于日常用品的清洁度要求越来越高。为了满足这一需求&#xff0c;超声波清洗机应运而生&#xff0c;以其高效、便捷的清洁方式赢得了广泛的市场。然而&#xff0c;面对市场上琳琅满目的超声波清洗机品牌和型号&#xff0c;很多时候都是无…

2047过滤空格(C语言)

目录 一&#xff1a;题目 二&#xff1a;思路分析 三&#xff1a;代码 一&#xff1a;题目 二&#xff1a;思路分析 1.首先&#xff0c;这道题是一个字符串的问题&#xff0c;我们要先知道字符串存放在char类型的数组中的&#xff0c;并不是一个变量就可直接存放的下一个完整…

iOS设备信息详解

文章目录 ID 体系iOS设备信息详解IDFA介绍特点IDFA新政前世今生获取方式 IDFV介绍获取方式 UUID介绍特点获取方式 UDID介绍获取方式 OpenUDID介绍 Bundle ID介绍分类其他 IP地址介绍获取方式 MAC地址介绍获取方式正常获取MAC地址获取对应Wi-Fi的MAC地址 系统版本获取方式 设备型…

使用 pytest.ini 文件控制输出 log 日志

一、前置说明 pytest.ini 文件中可以配置参数来控制 pytest 的运行行为,其存放路径要求与 conftest.py 一样。 项目根目录project_root/ ├── pytest.ini ├── tests/ │ └── test_demo.py以test开头的测试子目录project_root/ ├── tests/ │ ├── pytest.in…

Linux6.3、IO基础(文件描述符及分析系统接口细节)

个人主页&#xff1a;Lei宝啊 愿所有美好如期而遇 前言 我们介绍文件描述符的顺序是&#xff1a; 为什么我们新打开几个文件&#xff0c;open返回值fd从3开始&#xff1f;fd与FILE*的关系&#xff1f;fd的理解&#xff1f; 我们就很疑惑&#xff0c;0,1,2哪里去了&#xff…

【Linux系统编程】进程状态

介绍 进程的状态指的是进程在执行过程中所处的状态。进程的状态随着进程的执行和外界条件的变化而转换。我们可用 kill 命令来进程控制进程的状态。 kill中的 kill -l 指令用于查看系统中定义的所有信号及其对应的编号。这些信号可以用于 kill 命令来向进程发送特定的信号控制其…

地图服务器GeoServer的安装与配置

文章目录 1.安装配置Java2.安装配置Tomcat3 安装配置GeoServer GeoServer提供了多种安装配置方式&#xff0c;但是本质上GeoServer是一个基于Java Web的项目&#xff0c;因此我们理论上只需要安装Java&#xff0c;并且将其放置在一个Web服务器&#xff08;例如Apache Tomcat&am…

BioXCell--RecombiMAb anti-mouse VEGFR-2

DC101-CP132单克隆抗体是原始DC101单克隆的重组嵌合型抗体。可变结构域序列与原始DC101相同&#xff0c;但是恒定区序列已经从大鼠IgG1变为小鼠IgG2a。DC101-CP132单克隆抗体像原始大鼠IgG1抗体一样&#xff0c;不包含Fc突变。 DC101-CP132单克隆抗体能与小鼠VEGFR-2(血管内皮生…

等保测评里面,登录后,强制检测弱口令的处理流程

一张图脑补&#xff1a; 密码强度检查工具&#xff1a;https://blog.csdn.net/qq_37148232/article/details/135017666?spm1001.2014.3001.5501

目标检测-Two Stage-RCNN

文章目录 前言一、R-CNN的网络结构及步骤二、RCNN的创新点候选区域法特征提取-CNN网络 总结 前言 在前文&#xff1a;目标检测之序章-类别、必读论文和算法对比&#xff08;实时更新&#xff09;已经提到传统的目标检测算法的基本流程&#xff1a; 图像预处理 > 寻找候选区…

12.25

led.c #include "led.h" void all_led_init() {RCC_GPIO | (0X3<<4);//时钟使能GPIOE_MODER &(~(0X3<<20));//设置PE10输出GPIOE_MODER | (0X1<<20);//设置PE10为推挽输出GPIOE_OTYPER &(~(0x1<<10));//PE10为低速输出GPIOE_OSPEED…

虚拟机安装centos7系统步骤

1、下载系统镜像文件 下载地址&#xff1a;https://mirrors.aliyun.com/centos/7.9.2009/isos/x86_64/CentOS-7-x86_64-DVD-2207-02.iso 2、鼠标右键点击虚拟机-->设置-->CD/DVDD-->使用ISO映像文件-->点击浏览&#xff0c;选择文件&#xff0c;而后保存设置 3、点…

蓝桥杯c/c++程序设计——冶炼金属

冶炼金属 问题描述 小蓝有一个神奇的炉子用于将普通金属 O 冶炼成为一种特殊金属 X。这个炉子有一个称作转换率的属性 V&#xff0c;V 是一个正整数&#xff0c;这意味着消耗 V 个普通金属 O 恰好可以冶炼出一个特殊金属 X&#xff0c;当普通金属 O 的数目不足 V 时&#xff0…

【STM32单片机】汉诺塔游戏

文章目录 一、功能简介二、软件设计三、实验现象联系作者 一、功能简介 本项目使用STM32F103C8T6单片机控制器&#xff0c;IIC OLED液晶、按键等。 主要功能&#xff1a; 系统运行后&#xff0c;OLED显示游戏画面&#xff0c;可通过K1或K3键选择关卡&#xff0c;K2键开始。 二…