💯中缀表达式转后缀表达式（机算）

思路：

根据 括号 > 乘除 > 加减 的原则，在从左往右扫描表达式的过程中，确定表达式操作符的运算顺序，

先初始化一个栈，栈中用来存储“暂时无法确定运算顺序的操作符” 和 “左括号”。

机器扫描顺序是从左往右，因此每得到一个运算顺序，就可以确定一部分后缀表达式，

• 在不遇到括号情况下，需要多次判断加减乘除计算顺序，在每一次判断依赖当前扫描到的操作符和前面一个操作符，将整个表达式看做[已经转换为后缀表达式的部分——NumA] [前一个运算符op_prior] [一个单独的数字 NumB] [当前扫描到的运算符op_present] [尚未参与转换的部分 NumC] 的样式。

  [NumA] [op_prior] [NumB] [op_present] [NumC]			// 每一步的形式
  

  此时 op_prior 在栈顶（后面会解释为什么它在栈顶），循环扫描至 op_present 操作符。

  每一步中，两个操作符的优先级将决定 op_prior是否能弹出栈参与运算。（这也是每一步的本质工作）

  若 op_prior 运算优先级 >= op_present（另一种情况便是不能弹出 op_prior，此时它的有缘人便是右括号或循环结束），按照左优先原则，需先计算前面 A op_prior B 部分，从而op_prior 能弹出栈参与运算，将 op_prior 弹出并加入后缀表达式尾部： NumA NumB op_prior，这部分可视作一个操作数 NumA1 。

  此时整体表达式形式变为 [NumA1] [op_present] [NumC]。

  前面提到过 NumC 是尚未参与转换的部分（形式为Num1 op1 Num2 op2 ...），我们将再 NumC 中 num1、op1 和剩余部分视作 [Num1] [op1] [剩余部分Num2 op2 ...] 的形式。

  此时整体表达式便可视作 [NumA1] [op_present] [Num1] [op1] [Num2 op2 ...]。

  这就变成了 我们最开始想要的 [NumA] [op_prior] [NumB] [op_present] [NumC] 的形式。

  此时原先的 op_present 将被视作新的 “op_prior” ，如果不依靠后面的操作符，无法得出**“NumA NumB”以何种顺序进行计算**，因此它是上面初始化栈时提到的“暂时无法确定运算顺序的操作符”，将其入栈。

  开始新的循环，重复以上步骤直至结束。

  【注】虽然每一步形式如 [NumA] [op_prior] [NumB] [op_present] [NumC] ，但是实质上每次比较的是 当前扫描的运算符和栈中暂时无法确定运算顺序的运算符。

• 在遇到括号时，遇到左括号压入栈顶，括号内部格式仍然符合上述形式，按上述执行，直至遇到右括号，弹出栈中运算符加入到后缀表达式中，再弹出左括号，表明结束了该组括号的匹配。

算法如下：

初始化一个栈，栈中用来存储“暂时无法确定运算顺序的操作符” 和 “左括号”。

1. 从左往右扫描表达式的每一个元素，有 3 种情况：

   • 遇到 操作数 ，直接加入后缀表达式中。

   • 遇到 界限符（括号）:

     • 左括号：

       直接压入栈顶，等待一个右括号与其匹配，匹配到后，便可将括号里内容看做一个操作数加入到后缀表达式中。

     • 右括号：

       弹出栈顶操作符并将其加入后缀表达式，重复，直至遇到与其匹配的左括号，将左括号弹出，左括号不加入后缀表达式。

   • 遇到 操作符 ：依次弹出栈中 优先级高于或等于 当前操作符的所有操作符，弹出时依次加入后缀表达式，直至栈顶元素为左括号或栈空为止。此时将当前操作符入栈。

     【注】上面的优先级指的是：* = / > + = -

2. 扫描结束后，将栈中剩余运算符依次弹出、加入后缀表达式。