资源描述:
《数据结构与算法问题分析及源代码之表达式求值》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、表达式求值1题目以字符序列输入一包括加、减、乘、除的正确的四则运算算式(可以包含括号,不包含变量和函数调用),编写程序,利用栈等将中缀表达式转换为后缀表达式并计算该表达式的值。、2目的输入任意合法含括号的四则运算结果,熟悉栈的相关操作与应用。3设计思想用两个堆栈分别存储表达式的数据和运算符,用一个变量来表示运算符的优先级,四则运算时,若后读入的运算符优先级高于前一个运算符,那么就在该运算下计算后两个数据的值,如此直至运算符堆栈为空。用一个变量标记括号,遇到括号则标记加1,每出栈一对括号则标记减1,结合该标号判断运算符的出栈时机。5程序流程图>=<数据初始化strcpy(TempData,"
2、")*c!='#'
3、
4、OPTR->c!='#'!In(*c,OPSET)Dr[0]=*cc++strcat(TempData,Dr)In(*c,OPSET)Data=atof(TempData)OPND=Push(OPND,Data)strcpy(TempData," ")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,
5、b))返回OPND->f6源程序#include"stack.h"intis_Operator(charOperator)//判断是不是操作符{switch(Operator){case'+':case'-':case'*':case'/':case'(':case')':return1;default:return0;}}intpriority(charOperator)//判断符号优先级{switch(Operator){case'+':case'-':return1;case'*':case'/':return2;case'(':case')':return3;default:retur
6、n0;}}inttwo_result(intOperator,intoperand1,intoperand2)//求出堆栈中两个数的值{switch(Operator){case'+':return(operand2+operand1);case'-':return(operand2-operand1);case'*':return(operand2*operand1);case'/':return(operand2/operand1);}}intcalculate(char*expression){LinkStackOperator=InitStack(Operator);LinkStack
7、operand=InitStack(operand);intposition=0;intop=0;intoperand1=0;intoperand2=0;intevaluate=0;boolsign=0;//标记左括号while(expression[position]!=' '&&expression[position]!=''){if(!is_Operator(expression[position])){Push(operand,int(expression[position])-48);position++;}elseif(StackEmpty(Operator)){Push(O
8、perator,int(expression[position]));position++;}elseif(priority(expression[position])>priority(Operator->data)){Push(Operator,int(expression[position]));if(expression[position]=='(')sign=1;if(expression[position]==')'){Pop(Operator,&op);//Pop')'Pop(Operator,&op);Pop(operand,&operand1);Pop(operand,&op
9、erand2);operand=Push(operand,two_result(op,operand1,operand2));Pop(Operator,&op);//Pop'('}position++;}elseif(!sign){operand=Pop(operand,&operand1);operand=Pop(operand,&operand2);Operator=Pop(Operator,