《数据结构与算法问题分析及源代码之表达式求值.doc》由会员分享，可在线阅读，更多相关《数据结构与算法问题分析及源代码之表达式求值.doc（5页珍藏版）》请在金锄头文库上搜索。
1、表达式求值1 题目以字符序列输入一包括加、减、乘、除的正确的四则运算算式（可以包含括号，不包含变量和函数调用），编写程序，利用栈等将中缀表达式转换为后缀表达式并计算该表达式的值。、2 目的输入任意合法含括号的四则运算结果，熟悉栈的相关操作与应用。3 设计思想用两个堆栈分别存储表达式的数据和运算符，用一个变量来表示运算符的优先级，四则运算时，若后读入的运算符优先级高于前一个运算符，那么就在该运算下计算后两个数据的值，如此直至运算符堆栈为空。用一个变量标记括号，遇到括号则标记加1，每出栈一对括号则标记减1，结合该标号判断运算符的出栈时机。5 程序流程图=c!=#!In(*c, OPSET)Dr0=
2、*cc+strcat(TempData,Dr)In(*c, OPSET)Data=atof(TempData)OPND=Push(OPND, Data)strcpy(TempData,0)precede(OPTR-c, *c)OPTR=Push(OPTR, *c)OPTR=Pop(OPTR)theta=OPTR-c;OPTR=Pop(OPTR)c+b=OPND-fc+OPND=Pop(OPND)a=OPND-fOPND=Pop(OPND)OPND=Push(OPND, Operate(a, theta, b)返回OPND-f6 源程序#include stack.h int is_Operat
3、or(char Operator) /判断是不是操作符 switch(Operator) case +: case -: case *: case /: case (: case ): return 1; default: return 0; int priority(char Operator) /判断符号优先级 switch(Operator) case + : case - : return 1; case * : case / : return 2; case ( :case ) : return 3; default : return 0; int two_result(int Op
4、erator,int operand1,int operand2) /求出堆栈中两个数的值 switch(Operator) case +: return (operand2+operand1); case -: return (operand2-operand1); case *: return (operand2*operand1); case /: return (operand2/operand1); intcalculate(char *expression) LinkStack Operator=InitStack(Operator); LinkStack operand=Init
5、Stack(operand); int position=0; int op=0; int operand1=0; int operand2=0; int evaluate=0; bool sign=0;/标记左括号 while(expressionposition!=0&expressionposition!=n) if(!is_Operator(expressionposition) Push(operand,int(expressionposition)-48); position+; else if(StackEmpty(Operator) Push(Operator,int(expr
6、essionposition); position+; else if(priority(expressionposition)priority(Operator-data)Push(Operator,int(expressionposition); if(expressionposition=()sign=1;if(expressionposition=)Pop(Operator,&op);/Pop)Pop(Operator,&op);Pop(operand,&operand1);Pop(operand,&operand2);operand=Push(operand,two_result(o
7、p,operand1,operand2);Pop(Operator,&op);/Pop( position+; else if(!sign) operand=Pop(operand,&operand1); operand=Pop(operand,&operand2); Operator=Pop(Operator,&op); operand=Push(operand,two_result(op,operand1,operand2); else Push(Operator,expressionposition); position+; while(!StackEmpty(Operator) ope
8、rand=Pop(operand,&operand1); operand=Pop(operand,&operand2); Operator=Pop(Operator,&op); operand=Push(operand,two_result(op,operand1,operand2); operand=Pop(operand,&evaluate); return evaluate;#include #include #include calculate.hvoid main() char expression50; printf(输入四整数则运算表达式：n); gets(expression); printf(计算结果： %s = %dn,expression,calculate(expression);
