逆波兰表达式的处理方式
逆波兰表达式
逆波兰表达式就是后缀表达式。我们平常写出来计算的是中缀表达式。
中缀表达式—> 二叉语法树
先加括号至级别相等的两部分，op作为根，前部分为左子树，后部分为右子树。然后依次往下剥，如果出现同等级多部分，按前面的先计算为准，继续加括号，直至分为两部分。
此语法树叶子结点均为数，非叶子结点均为op，得此语法树后先序遍历为前缀表达式，后续遍历为后缀表达式。
前缀表达式计算：
- 从前往后遍历串，遍历的过程中，如果一个符号后有两个数，则用这两个数用前面的符号进行计算，然后再用结果替换op和那两个数，再次循环操作。
- 从后往前遍历，遇到数就进栈，遇到op就出栈两个数计算，结果进栈，最后栈顶元素就是结果。
后缀表达式计算：
从前往后遍历，遇到数字进栈，遇到OP出栈两个数，将计算结果入栈，最后其栈顶为结果。
中缀表达式转后缀表达式：
- 从左往右依次遍历
- 运算数直接输出
- 左括号，直接压入栈(括号是最高优先级，无序比较，入栈后优先级降到最低，确保其他符号正常入栈)
- 右括号，(意味着括号已经结束)不断弹出栈顶云算符，直到遇到左括号(弹出但不输出)
- 运算符，将该运算符与栈顶运算符进行比较。
- 如果运算符优先级高于栈顶运算符则压入栈
- 如果运算符优先级低于等于栈顶运算符则弹出栈顶运算符，然后比较新的栈顶云算符直到优先级大于栈顶云算符或者是栈空，在将该运算符入栈。
- 如果对象处理完毕，则依次弹出并输出所有运算符。
依然是一上面的例子为例分析这一步骤：
8-(3+5)*(5-6÷2)
- 8 直接输出 8
- - 栈为空，入栈
- ( 直接入栈，且认为优先级最低
- 3 直接输出 8 3
- + 此时栈顶元素为( ，高于栈顶运算符优先级，入栈
- 5 直接输出 8 3 5
- ） 依次弹出栈中元素，弹出+ 直到遇到 ） 8 3 5 +
- * 此时栈顶元素为-，优先级高于栈顶元素，入栈
- ( 入栈
- 5 直接输出 8 3 5 + 5
- - 栈顶元素为( ，优先级高，入栈
- 6 直接输出 8 3 5 + 5 6
- ÷ 栈顶元素为 - ，优先级高于栈顶元素，入栈
- 2 直接输出 8 3 5 + 5 6 2
- ) 弹出栈，直到遇到( ，输出 8 3 5 + 5 6 2 ÷ -
- 然后依次出栈中所有元素，直到栈空，输出8 3 5 + 5 6 2 ÷ - * -