《C语言后缀表达式计算》由会员分享，可在线阅读，更多相关《C语言后缀表达式计算（33页珍藏版）》请在金锄头文库上搜索。
1、.一、设计思想计算算数表达式并求值，采取的共有两种方法：1. 先将算数表达式转化为后缀表达式，然后对后缀表达式进行计算。2. 对算数表达式进行直接的计算。第一种算法这种解决方案又分为两步：1.将表达式先转化为后缀表达式的字符串数组2.利用后缀表达式进行计算在转化过程中，第一，建立一个存符号的栈，和一个字符串数组，用来存放转化以后的表达式然后，对于得到的用户输入的字符串进行逐个的扫描，如果是数组或者小数点，则直接存放到数组中，并且在后面加入一个分隔符，如果是操作符，则和栈中的已存的进行比较，如果比栈中的操作符的优先级高，则直接入栈，如果优先级低或相等，则栈中元素出栈，存到字符串中，然后再次检查栈
2、顶，直到栈中元素的优先级低于扫描操作符，则此操作符入栈，然后扫描下一个字符，直到遇到字符串的结束符号0，扫描结束。数组中存的就是后缀表达式。得到后缀表达式后，进行计算，要用到数值栈。首先要将字符表示的数字转化为浮点小数，然后进行扫描，遇到数值，放入栈中，遇到操作符，就从栈中取出两个数，进行计算后再放入栈中，扫描下一个，最后的计算结果就存到了栈中，直接取出栈内元素，就是计算的最后结果。第二种算发首先要建立两个栈，一个用来存放操作符，一个用来存放数值。开始对用户输入的字符串进行扫描，如果是数字字符或者小数点，则将字符转化为浮点数存到数栈里，如果是操作符，则观察符号栈，如果栈顶元素的优先级低于观察的
3、操作符，则操作符入栈，如果栈顶元素的优先级高于或者等于观察的操作符，则从数值栈中取出两个浮点数，从符号栈中取出栈顶的操作符，然后进行相应的数值计算，所得的结果再存到数值栈中，重复这样的操作，直到符号栈中栈顶元素的优先级低于观察的操作符，则此操作符入栈，然后对下一个字符进行扫描。如果是左括号，则不进行优先级的比较，直接入栈，入栈后优先级为-1。如果是右括号，则从数值栈中取两个操作数，符号栈中取出一个符号，然后进行计算后得数放入数栈中，不断进行此类操作，直到从栈中取出的是左括号为止，左括号去掉，扫描下一个。扫描结束后，计算也结束了，计算的结果就存放在数值栈中，最后把数值栈中的数取出，就是所得的计算
4、结果。容错的算法简要：括号匹配：当扫描到左括号是，左括号直接入栈，扫描到右括号时，则左括号出栈，如果栈为空，则右括号多，如果最后栈中还有括号，则左括号多。给出错误提示。除数不为0：当扫描到/时，就判断其后面的数字是否为0，如果为0报错。取余运算：取余运算时，操作数判断是否为整数，不为整数报错。二、算法流程图第一种算法:先将表达式转化为后缀表达式，然后计算其主函数流程图为： 得到用户输入的中缀表达式调用容错函数存在错误 报错并结束无错调用函数得到后缀表达式后缀表达式的计算返回计算结果调用直接计算的函数返回直接计算的结果图1 主函数算法流程图其中将中缀表达式转化为后缀表达式的主要流程为：取得字符并
5、判断如果是数字或小数点直接放入字符数组中在其后加入分隔符如果是操作符与栈顶比较判断哪类括号直接入栈右括号取出不为(从栈中取出操作符放入数组直接入栈优先级高于栈顶如果是括号出栈存入数组中左括号优先级不高于栈顶图2 中缀转化为后缀算法流程图后缀表达式的计算，实现的流程图为：从数栈取2个数做相应计算结果存入数栈判断符号类型得到后缀表达式数字字符操作符转化为浮点数入栈从数栈中取出计算结果作为返回值图3 后缀表达式计算算法流程图下面介绍直接计算出结果的算法的实现：栈非空栈空低于栈顶高于栈顶NOYES左括号得到中缀表达式从字符串中取出一个字符判断字符类型数字字符操作符转化为浮点数入栈括号括号类型直接入栈右
6、括号从栈中取出操作符是否为（丢弃（放入数组与栈顶比较直接入栈取出栈顶两个数作相应计算结果存入数栈符号栈是否为空将数值栈顶返回取栈顶符号与2个数计算，结果存入数值栈图4 直接计算中缀表达式算法流程图三、源代码下面给出的是用先转后缀再计算和直接计算的算法实现的程序的源代码：#include /*导入需要用到的各种包*/#include#includetypedef struct /*定义结构体用来存储操作符*/char op; /*存储字符*/int level; /*存储优先级*/OpNode;typedef struct OpNode op100; int top; int size; /*表
7、示栈内元素的个数*/ stack; /*定义符号栈*/void init(stack *st) /*初始化栈*/ st-size=0; st-top=0;OpNode pop(stack *a) / *出栈*/ if (a-size=0) /*如果栈为空结束操作*/ exit(-1); a-size-; return a-op-(a-top); /*取出栈顶元素*/void push(stack *a,OpNode op) /*入栈函数*/ a-size+; a-op(a-top)+=op;OpNode top(stack *a) /*观察栈顶函数*/ if (a-size=0) /*如果栈为
8、空结束操作*/ printf(stack is emptyn); exit(-1); return a-op(a-top)-1; /*只得到栈顶的值而不出栈*/typedef struct /*定义数值栈*/ double num100; int top; /*栈顶指针*/ int size; numstack;void init2(numstack *st) /*初始化数值栈*/ st-size=0; st-top=0;double pop2(numstack *a) /*数值栈出栈*/ if (a-size=0) /*出栈前的判空*/ exit(-1); a-size-; return a
9、-num-(a-top); /*得到栈顶的值*/void push2(numstack *a,double num) /*入栈*/ a-size+; a-num(a-top)+=num;void main() /*主函数*/ void change (char str,char exp); /*声明要用到的各个函数*/ double CalResult(char exp); /*声明后缀表达式的计算函数*/ double Directcalresult(char str); int check(char str,char chestr100); char str100,exp100,chest
10、r100; /*str存储原算术表达式，exp存储对应的 printf(算术表达式为:n); 后缀表达式,chestr存储容错字符*/ gets(str); if(check(str,chestr) /*调用容错函数*/ printf(表达式错在：n); printf(%sn,str); printf(chestr); /*根据输入情况指出错误的地方*/ exit(-1); change(str,exp); /*调用函数将中缀转化为后缀*/ printf(后缀表达式为:%sn,exp); printf(运算结果为： %fn,CalResult(exp); /*调用函数计算后缀表达式*/ printf(直接运算的结果为: %fn,Directcalresult(str); /*调用直接计算函数*/void change (char str,char ch) /*将前缀表达式转化为后缀表达式*/int i=0; /*str的索引*/int k=0;char c; /*字符串中取出的放在C中*/stack st; /*定义符号栈*/OpNode op;OpNode ops;init(&st); /*初始化符号栈*/c=stri+; while (c!=0) /*对字符串进行扫描*/if ( (c=0&c=0&c=9)|c=.)
