一、前缀表达式

1.1、定义

前缀表达式又称波兰式，运算符位于操作数之前。

举例说明： ( 3 + 4 ) × 5 - 6 对应的前缀表达式： - × + 3 4 5 6

1.2、求值

从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素 和 次顶元素），并将结果入栈。

重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果。

例如:

3 + 4 - 6 / 2 对应的前缀表达式：- + 3 4 / 6 2 , 针对前缀表达式求值步骤如下:

1. 2、6依次入栈
2. 遇到 /，弹出6、2，计算6/2的结果，得3，3入栈
3. 4、3依次入栈，此时栈中元素，从栈底到栈顶依次为3、4、3
4. 遇到 +，弹出3、4，计算3+4的结果，得7，7入栈。此时栈中元素，从栈底到栈顶依次为7、3
5. 遇到 -，弹出7、3，计算7-3的结果，得4，4入栈
6. 最终结果：4

二、中缀表达式

2.1、定义

中缀表达式就是常见的运算表达式，如：( 3 + 4 ) × 5 - 6。

中缀表达式在计算结果时，往往转成其它表达式来操作(一般转成后缀表达式)。

2.2、求值

从左到右扫描该中缀表达式，定义2个栈(符号栈、运算数栈)：

1. 如果遇到运算数，直接入运算数栈。
2. 如果遇到左括号，直接入符号栈。
3. 如果遇到右括号，不断弹出符号栈元素，直至遇到左括号，左括号出栈。换句话说，执行一对括号内的所有运算符。弹出一个运算符，弹出2个运算数操作(栈顶是右操作数、次栈顶为左操作数)，将操作的结果入运算数栈。
4. 如果遇到其他运算符，不断弹出运算符优先级大于等于当前运算符的运算符。弹出一个运算符，弹出2个运算数操作(栈顶是右操作数、次栈顶为左操作数)，将操作的结果入运算数栈。最后，新的运算符入运算符栈。
5. 在处理完整个表达式之后，一些运算符可能仍然在符号栈中，因此把栈中剩下的符号依次输出，弹出一个运算符，弹出2个运算数操作(栈顶是右操作数、次栈顶为左操作数)，将操作的结果入运算数栈。
6. 表达式转换结束。

三、后缀表达式

3.1、定义

后缀表达式又称逆波兰表达式，运算符位于操作数之后。

举例说明： ( 3 + 4 ) × 5 - 6 对应的后缀表达式： 3 4 + 5 × 6 –

3.2、求值

从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素 和 栈顶元素），并将结果入栈。

重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果。

例如:

( 8 + 2 ) / 5 - 6 对应的后缀表达式：8 2 + 5 / 6 - , 针对前缀表达式求值步骤如下:

1. 8、2依次入栈
2. 遇到 +，弹出2、8，计算8+2的结果，得10，10入栈
3. 5入栈，此时栈中元素，从栈底到栈顶依次为10、5
4. 遇到 /，弹出5、10，计算10/5的结果，得2，2入栈。
5. 6入栈，此时栈中元素，从栈底到栈顶依次为2、6
6. 遇到 -，弹出6、2，计算2-6的结果，得-4，-4入栈
7. 最终结果：-4

四、转换

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

从左到右进行遍历，定义2个栈(结果栈、运算符栈)：

1. 遇到的是运算数，直接压入结果栈。

2. 遇到的是左括号’('，直接压入运算符栈(括号是最高优先级，无需比较；入栈后优先级降到最低，确保其他符号正常入栈)。

3. 遇到的是右括号’)'，意味着括号已结束。不断弹出运算符栈并压入结果栈，直到遇到左括号，这个左括号弹出但是不压入。

4. 遇到的是运算符(‘+’、‘-’、‘*’、‘/’)，有三种情况：
   ①如果运算符栈为空，直接入栈
   ②如果运算符栈栈顶元素是左括号’('，直接入栈
   ③如果运算符栈栈顶元素是运算符，则需要进行比较：
        1. 如果优先级大于栈顶运算符，则压入运算符栈
        2. 如果优先级小于等于栈顶运算符，则将栈顶运算符弹出并压入结果栈，然后比较新的栈顶运算符，直到优先级大于栈顶运算符或者栈空，再将该运算符入运算符栈

5. 将运算符栈中剩余的全部压入结果栈。

6. 结果栈从栈底到栈顶的序列就是最终结果，后缀表达式。

4.2、中缀表达式转前缀表达式

从右到左进行遍历，定义2个栈(结果栈、运算符栈)：

1. 遇到的是运算数，直接压入结果栈。

2. 遇到的是右括号’)'，直接压入运算符栈(括号是最高优先级，无需比较；入栈后优先级降到最低，确保其他符号正常入栈)。

3. 遇到的是右括号’('，意味着括号已结束。不断弹出运算符栈并压入结果栈，直到遇到右括号，这个右括号弹出但是不压入。

4. 遇到的是运算符(‘+’、‘-’、‘*’、‘/’)，有三种情况：
   ①如果运算符栈为空，直接入栈
   ②如果运算符栈栈顶元素是右括号’)'，直接入栈
   ③如果运算符栈栈顶元素是运算符，则需要进行比较：
        1. 如果优先级大于栈顶运算符，则压入运算符栈
        2. 如果优先级小于等于栈顶运算符，则将栈顶运算符弹出并压入结果栈，然后比较新的栈顶运算符，直到优先级大于栈顶运算符或者栈空，再将该运算符入运算符栈

5. 将运算符栈中剩余的全部压入结果栈。

6. 结果栈从栈顶到栈低的序列就是最终结果，前缀表达式。