神机百炼1.27-RPN逆波兰表达式

RPN逆波兰表达式

• • 食用指南：
  • 题目描述：
  • 题目分析：
  • 算法原理：
  • • 模板算法：
    • 逆波兰表达式：
    • • 1. 初始化：
      • 1. 运算符栈op：
      • 2. 计算数栈num：
  • 算法核心：
  • • 1. 计算过程：
    • 2. 函数抽象：
    • 3. 关注点：op出栈
  • 代码实现：
  • 代码误区：
  • • 1. 遍历完毕计算式，清空op栈过程中也在清空num栈：
    • 2. 易错点：计算数摆放顺序
    • 3. 计算后缀表达式时，计算符何时出op栈?
    • 4. 计算最终结果时，计算数何时出num栈？
    • 5. 时间复杂度：
• 本篇感想：

食用指南：

对该算法程序编写以及踩坑点很熟悉的同学可以直接跳转到代码模板查看完整代码
只有基础算法的题目会有关于该算法的原理，实现步骤，代码注意点，代码模板，代码误区的讲解
非基础算法的题目侧重题目分析，代码实现，以及必要的代码理解误区

题目描述：

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

  注意：

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

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

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

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

• 题目来源：https://www.acwing.com/problem/content/3305/

题目分析：

• 逆波兰表达式：
  波兰逻辑学家J・卢卡西维兹发明
  让计算机理解 + - * / ()的优先级运算顺序

  逆波兰表达式包含两步：中缀表达式转后缀表达式 & 后缀表达式计算结果
  这两步都围绕着栈这一数据结构

  第一步是在调整计算顺序
  第二步是在按照顺序求出结果

• 负号只能作为减号出现，若作为负号出现则严重干扰数据读取

  下面我们来讲解带有括号的逆波兰表达式

算法原理： 模板算法：

• 传送门：静态栈

逆波兰表达式： 1. 初始化：

• 双栈：一个计算数栈num，一个运算符栈op

  两栈都在遍历计算式字符串时进行入栈出栈操作

  遍历完计算式字符串后，双栈也需要出空，最终结果就是num栈最后一个出栈的元素

• 优先级：
  unordered_map，以运算符为键，优先级为值，一次存多对键值对

• 获取完整计算数：

  利用中的isdigit()函数判断当前字符是否为数字

  从第一个是数字的元素遍历到第一个非数字的元素，中间的字符串就是完整数字字符串
  利用x = x*10 + string[i] - ‘0’;即可获取完整数字

1. 运算符栈op：

• 作用：
  计算机本身不知道运算符还有优先级
  需要我们自己调整运算符号的顺序，以达到优先级的效果
  所以op栈针对运算符进行顺序调整

• 入op栈：

  一种情况：

  遍历运算式字符串时，每遍历到一个运算符，等待栈顶元素出栈完毕后该运算符入栈

  若该运算符为右括号)，则)不入栈，只进行栈顶出栈即可

• 出op栈：

  三种情况：

  1. 当)准备入栈，栈顶出栈，直到(也出栈
  2. 入栈元素优先级小于等于栈顶元素，栈顶元素需要出栈，
     直到栈空或栈顶优先级小于入栈元素之后，入栈元素入栈
  3. 遍历完毕计算式字符串时，op栈全部出栈

• 模拟过程：

  三大出栈：
  

2. 计算数栈num：

• 作用：
  结合op栈的出栈运算符进行计算数的计算，求最终结果

• 入num栈：

  两种情况入栈：

  1. 遍历计算式时，遇到运算数则入num栈
  2. op栈出栈运算符时，num栈先出栈 两数参与运算，结果入num栈

• 出num栈：

  两种情况出栈：

  1. 遍历运算式时，发生op栈运算符出栈，
     此时num栈顶两元素出栈参与该运算符运算，结果入栈
  2. 遍历完运算式时，清空num栈内结果数

• 计算：
  op栈发生运算符出栈，则num栈出栈两数配合op运算
  num栈顶元素A作为被操作数
  num栈次顶元素B作为操作数
  计算 B ±*/ A，而非A ±*/ B

• 模拟过程：
  

算法核心： 1. 计算过程：

• 所有进出栈统一调度于 计算式的遍历

• 计算本身只发生在op栈栈顶出栈

• 每次只针对num栈栈顶两元素进行运算

• num栈的进出栈几乎完全被动于op栈的出栈

2. 函数抽象：

• 计算函数eval()：计算数为num栈顶两数，计算符为op栈栈顶符号
  计算完成后op出栈，结果入num栈
• 计算发生时刻：
  1. 遍历到)，op出栈
  2. op栈顶优先级 >= 当前遍历到的符号优先级，op出栈
  3. 遍历完毕计算式，op出栈
• num栈唯一主动：
  遍历计算式时，遇到数字，数字入栈

3. 关注点：op出栈

• 是op出栈推动的计算进行，我们写代码只需要关注这一点
  让num栈配合op即可

代码实现：

#include 
#include 
#include 
#include 
using namespace std;

stack num;
stack op;

//优先级表
unordered_map priority{ {'+', 1}, {'-', 1}, {'*',2}, {'/', 2} };

//num栈栈顶元素进行计算
void eval()
{
    int a = num.top();//被计算数
    num.pop();

    int b = num.top();//计算数
    num.pop();

    char p = op.top();//运算符
    op.pop();
	
	//注意点1：操作数顺序
    if (p == '+') num.push(b+a);;
    if (p == '-') num.push(b-a);;
    if (p == '*') num.push(b*a);;
    if (p == '/') num.push(b/a);;
}

int main()
{
    string s;//读入表达式
    cin >> s;
    
    for (int i = 0; i < s.size(); i++)
    {
    	//注意点2：完整数值获取
        if (isdigit(s[i]))
        {
            int x = 0, j = i;//计算数字
            while (j < s.size() && isdigit(s[j]))
            {
                x = x * 10 + s[j] - '0';
                j++;
            }
            num.push(x);//数字入栈
            i = j - 1;
        }
        
        if (s[i] == ')')
        {
            while(op.top() != '(')
                eval();
            op.pop();
        }else if (s[i] == '('){
        	op.push(s[i]);
        }else
        {
        	//注意点3：栈空 或 顶小于s[i] 时，s[i]入栈
            while (op.size() && priority[op.top()] >= h[s[i]])
                eval();
            op.push(s[i]);//操作符入栈
        }
    }
    //注意点4：清空op栈
    while (op.size()) 
    	eval();
    	
    cout << num.top() << endl;//最终结果也不必出栈，直接输出
    return 0;
}

代码误区： 1. 遍历完毕计算式，清空op栈过程中也在清空num栈：

• 先op继续运算，num配合出计算数收结果数
• 最后num仅余一数，即结果
• 由于num被动于op，所以读入数字后整个过程只需要关注op

2. 易错点：计算数摆放顺序

• 栈顶元素在左，栈顶下一元素在右
• 一旦摆放错误，结果必然不对

3. 计算后缀表达式时，计算符何时出op栈?

1. 遇到右括号)就出栈，直到左括号(出栈
2. s[i]优先级小于等于栈顶优先级，先栈顶出栈直到栈空或top优先级小于s[i]，s[i]才能入栈
3. 遍历完计算式，将op栈清空

4. 计算最终结果时，计算数何时出num栈？

1. op栈顶计算符出栈，则num栈顶连出两数参与运算

5. 时间复杂度：

• 不论是op出入栈，亦或num出入栈
  都是随着遍历计算式字符串进行对应操作

  换句话说，所有操作由计算式字符串统一指挥
  故时间复杂度是O(n)

本篇感想：

• 逆波兰表达式是栈的经典应用了
  双栈结构 + 优先级制度
  随着遍历计算式，num配合op出栈进行运算
  关注点主要在op栈的出栈

• 第一周结束了，共发了27篇博客，不是很理想
  前100篇博客是算法的基础模板，是筑基期，需要稳扎稳打
  后面的刷题博客肯定要加速，一天十篇不为过

• 这学期期末前不会更新C,JAVA,cpp语言，
  也不会介绍进程，网络，linux，数据库
  我期末应该在6月20 ~ 6月26，期末完后正好高考也完了，那会再系统地更新从c到框架

• 到35篇后应该进入图论，对dfs ,bfs不熟悉的同学看这里：【算法设计】用C++类和队列实现图搜索的广度优先遍历算法，先准备准备

• 看完本篇博客，恭喜已登 《练气境-后期》
  
  距离登仙境不远了，加油