1、用两种方式实现表达式自动计算 - 1 - 一、设计思想一、设计思想 （一）中缀转后缀的设计思想 设计一个能实现表达式自动求值计算，算术表达式由操作数、算符和括号组成。由于运 算符的优先级不同还要考虑括号。 所以表达式不可能一直的从左到右进行， 所以就借助栈来 实现这个表达式的求值。 首先要把算术表达式变换成与之等值的无括号表达式， 也就是中缀转后缀， 它也是这个 算法的关键。设计两个栈，一个为字符型的，存放运算符，用以将算术表达式变成无括号的 表达式；另一个浮点型的，存放操作数，用以对无符号的表达式进行求值。我们要假设运算 符的优先级：( ) , * /, + - 。首先将一左括号(入栈，作为
2、栈底元素；接着从左到右对算 术表达式进行扫描。每次读一位，若遇到左括号 （ ，则进栈；若遇到的是操作数，则立即 输出；若又遇到运算符，如果它的优先级比栈顶元素的优先级数高的话，则直接进栈，否则 输出栈顶元素， 直到新的栈顶元素的优先级数比它低的， 然后将它压栈； 若遇到是右括号 ） ， 则将栈顶的运算符输出，直到栈顶的元素为 （ ，然后，左右括号互相底消；到设计的结束 标志的时候表示表达式已经扫描完毕，表达式已经全部输入，将栈中的运算符全部输出，删 除栈底的左括号。以上完成了中缀表达式转后缀表达式，输出无括号的后缀表达式。 读后缀表达式，若遇数值，操作数进栈；若遇运算符，让操作数栈的栈顶和次栈
3、顶依次 出栈并与此运算符进行运算，运算结果入操作数栈；重复这个步骤，直到遇到结束标志，则 此时栈中的结果便是所求的后缀表达式的值， 接着输出结果。 以上就是设计这个算法的主要 的思想。 (二) 直接计算的设计思想 直接计算其实跟上一个相似，它是在上面扫两遍的思想进行修改的得来。 首先，要建立两个栈，一个为字符型的，存放运算符，另一个浮点型的，存放操作数， 我们开始对表达式进行扫描。首先要确定运算符的优先级： （、 ） 、*、/、+、-。如果扫描到 的是数字符号，把它们转换成浮点型数据或其他可运算的数据类型，存入操作数栈中。如果 扫描到的是运算符号，第一个运算符进栈，遇到 （存入运算符栈中，我们
4、按照第一种算 法的方法将表达式依次扫描。只不过不同的是，当每取得的一个运算符的时候，都要与栈顶 的运算符进行比较， 如果它的优先级小于栈顶运算符优先级时， 取出栈顶运算符并从操作数 栈中取栈顶两个数进行运算，得到的结果则要存回操作数栈，就这样边扫描边比较，再进行 计算。遇到“） ”对运算符的处理相同。扫描结束后，把运算符栈的元素和操作数栈里的数 进行运算。每次的运算结果再放入操作数栈，一直到计算到运算符栈空。最后操作数栈的栈 顶留下的操作数即表达式的计算结果。以上就是直接计算表达式的思路。 用两种方式实现表达式自动计算 - 2 - 二、算法流程图二、算法流程图 （一）中缀转后缀算法的流程图 输
5、入 输入表达式 判断数组 整数 转化成浮点型 小数 操作符 后缀数组 优先级大于栈 顶 操作符进栈 读完表达式 后缀表达 式 输出 是 优先级大于 栈顶或栈空 否 出栈 是 判断数组数 读表达式 操作符 操作数栈 计算结果 2个 数 1个 符 号 图 1中缀转后缀算法的流程图 流程图说明：该流程图分两部分成，第一部分是中缀转后缀部分，第二部分是用于后 缀表达式求值的。 用两种方式实现表达式自动计算 - 3 - （二）直接计算算法的流程图 输入 输入表达式 判断数组 转化成浮点型 数 操作符 操作数栈 计算结果 优先级大于栈 顶 操作符进栈 输出 是 优先级大于 栈顶或栈空 否 出栈(1个) 2
6、 个 数 图 2接计算算法的流程图 流程图说明：该流程图进过图 1 改进得到，只是缺少中缀转后缀的部分。 三、源代码三、源代码 下面给出的是用中缀转后缀算法实现的程序的源代码： #include #define N 50 typedef struct StackArray float dataN; int top; StackArray; /*定义操作数栈*/ typedef struct StackChar char dataN; int top; 用两种方式实现表达式自动计算 - 4 - StackChar; /*定义操作符栈*/ StackArray *InitNum() /*初始化数值栈*/ StackArray *p = (StackArray *)malloc(sizeof(StackArray); /*取一段内存赋予数值栈*/ p-top=-1; return p; /*返回*/ StackChar *InitChar() /*初始化操作符栈*
