算术表达式求值算法 中缀表达式

所谓表达式的求值就是从键盘上输入一个四则运算表达式按下Enter后在屏幕上输出表达式的结果。表达式的求值在计算机的应用中非常广泛，例如编译器中对所写的程序表达式的编译等。它也是数据结构课程中栈这一章节中非常重要的一个算法，通过实现这个算法可以更好的掌握和理解栈的相关操作。
中缀表达式是指运算符在运算数的中间，计算中缀表达式时需要用到两个栈：数字栈和运算符栈。在整个中缀表达式求值的过程中主要涉及到的模块有：栈的相关操作、优先级表的确立、输入的待计算字符串拆分为数字和运算符以及运算处理等。
一）、整体算法思路
1）、设立操作数栈和运算符栈，设表达式结束的标志是字符#，运算符栈底初始化为#，约定#运算符的优先级最小（这样做的目的是在当两个#相遇时就可以确定表达式扫描结束了）。
2）、若当前扫描到的是操作数则果断将此数压栈进操作数栈，如果当前是符号栈则将该操作符和栈顶操作符进行优先级比较如果低于栈顶优先级则将操作符栈顶元素弹出并弹出两个操作数进行运算，运算完毕将结果压入栈中。如果当前符号的优先级高于栈顶优先级则将此运算符入栈。
3）、循环操作2直到输入的表达式运算结束（运算符栈底的#和输入的表达式的#相遇）此时如若操作数栈中只剩一个数字则表示运算成功，此数就是表达式的结果，如果不止一个数则表示输入的表达式有误。