逆波兰表达式的处理方式

逆波兰表达式

逆波兰表达式就是后缀表达式。我们平常写出来计算的是中缀表达式。

中缀表达式—> 二叉语法树

先加括号至级别相等的两部分，op作为根，前部分为左子树，后部分为右子树。然后依次往下剥，如果出现同等级多部分，按前面的先计算为准，继续加括号，直至分为两部分。

此语法树叶子结点均为数，非叶子结点均为op，得此语法树后先序遍历为前缀表达式，后续遍历为后缀表达式。

前缀表达式计算：

•  从前往后遍历串，遍历的过程中，如果一个符号后有两个数，则用这两个数用前面的符号进行计算，然后再用结果替换op和那两个数，再次循环操作。
• 从后往前遍历，遇到数就进栈，遇到op就出栈两个数计算，结果进栈，最后栈顶元素就是结果。

后缀表达式计算：

       从前往后遍历，遇到数字进栈，遇到OP出栈两个数，将计算结果入栈，最后其栈顶为结果。

中缀表达式转后缀表达式：

• 从左往右依次遍历
• 运算数直接输出
• 左括号，直接压入栈(括号是最高优先级，无序比较，入栈后优先级降到最低，确保其他符号正常入栈)
• 右括号，(意味着括号已经结束)不断弹出栈顶云算符，直到遇到左括号(弹出但不输出)
• 运算符，将该运算符与栈顶运算符进行比较。
  1. 如果运算符优先级高于栈顶运算符则压入栈
  2. 如果运算符优先级低于等于栈顶运算符则弹出栈顶运算符，然后比较新的栈顶云算符直到优先级大于栈顶云算符或者是栈空，在将该运算符入栈。
• 如果对象处理完毕，则依次弹出并输出所有运算符。

依然是一上面的例子为例分析这一步骤：

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 ÷ - * -