计算表达式

1、 对于中缀表达式，两个栈，一个运算符栈，一个操作数栈。遇到数字则入栈，遇到操作符则比较操作符栈的栈顶元素，来决定是入栈还是进行运算。见数据结构教材P53

2、 为实现算符优先算法，可以使用两个工作栈。一个称做 OPTR, 用以寄存运算符；另 一个称做 OPND, 用以寄存操作数或运算结果。算法的基本思想是： (1) 首先置操作数栈为空栈，表达式起始符"#"为运算符栈的栈底元素； (2) 依次读入表达式中每个字符，若是操作数则进 OPND 栈，若是运算符则和 OPTR 栈的栈顶运算符比较优先权后作相应操作，直至整个表达式求值完毕（即 OPTR 栈的栈顶元素和当前读入的字符均为"# ")

2、后缀表达式，一个操作数栈  3 4 + 5 × 6 - ,

规则：从左到右遍历表达式的每个数字和符号，遇到是数字就进栈，遇到是符号，就将处于栈顶两个数字出栈，进行运算，运算结果进栈，一直到最终获得结果

3、从中缀表达式获得后缀表达式：一个运算符栈 (3+4)×5-6

**规则从左到右：**

- 如果当前元素为操作数，则将该元素直接存入到后缀表达式中
- 如果当前元素为“(”，则将其直接入栈；如果为“)”，则将栈中的操作符弹栈，并将弹栈的操作符存入到后缀表达式中，直至遇到“(”，将“(”从栈中弹出，并不将其存入到后缀表达式中
- 如果是其他操作符，如果其优先级**高于**栈顶操作符的优先级，则将其入栈，如果是**小于或等于**栈顶操作符优先级，则依次弹出栈顶操作符并存入后缀表达式中，直至遇到一个栈顶优先级小于当前元素优先级时或者栈顶元素为“(”或者栈为空为止，保持当前栈顶元素不变，并将当前元素入栈；（（**注意转换为前缀表达式时是优先级较高或相同，而这里则不包括相同的情况**））

（栈顶操作符的优先级大于此操作符，弹出栈顶操作符直至遇到“（”或者栈顶操作符的优先级小于此操作符；定义相等时栈顶操作符大于此操作符，继续弹出；）

4、前缀表达式求值，一个操作数栈**前缀表达式的计算机求值：（3+4)×5-6 对应的前缀表达式就是 - × + 3 4 5 6 ,**　　从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素 和 次顶元素），并将结果入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果

5、**将中缀表达式转换为前缀表达式(3+4)×5-6**

**转换步骤如下**:

1. 初始化两个栈:运算符栈s1，储存中间结果的栈s2
2. 从右至左扫描中缀表达式
3. 遇到操作数时，将其压入s2
4. 遇到运算符时，比较其与s1栈顶运算符的优先级
   1. 如果s1为空，或者栈顶运算符为右括号“)”，则直接将此运算符入栈
   2. 否则，若优先级比栈顶运算符的较高或相等，也将运算符压入s1
   3. 否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4-1)与s1中新的栈顶运算符相比较
5. 遇到括号时
   1. 如果是右括号“)”，则直接压入s1
   2. 如果是左括号“(”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到右括号为止，此时将这一对括号丢弃
6. 重复步骤2至5，直到表达式的最左边
7. 将s1中剩余的运算符依次弹出并压入s2
8. 依次弹出s2中的元素并输出，结果即为中缀表达式对应的前缀表达式（其实就一个栈，把结果最后逆序输出即可）

（其实相等归结于大于还是小于并没有区别）