《C语言后缀表达式计算》由会员分享，可在线阅读，更多相关《C语言后缀表达式计算（18页珍藏版）》请在金锄头文库上搜索。
1、word一、设计思想计算算数表达式并求值，采取的共有两种方法：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; /*表示栈内元素的个数*/ stack; /
7、*定义符号栈*/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) /*如果栈为空完毕操作*/ printf(stack
8、 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-num-(a-top); /*得到栈顶
9、的值*/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,chestr100; /*str存储原算术表达式，
10、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,Dir
11、ectcalresult(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=.) chk+=c; /*将字符直接放入数组中*/ c=stri+; chk+=|; /*在其后面放入一个分隔符*/if (c=() /*如果字符是左括号*/ op.op=(;
