1、需求分析
设计一个程序，演示用算符优先法对算术表达式求值的过程。利用算符优先关系，实现对算术四则混合运算表达式的求值。
（1）输入的形式：表达式，例如2*(3+4)
包含的运算符只能有'+' 、'-' 、'*' 、'/' 、'('、 ')'；
（2）输出的形式：运算结果，例如2*(3+4)=14；
（3）程序所能达到的功能：对表达式求值并输出
2、系统设计
1、栈的抽象数据类型定义：
ADT Stack{
数据对象：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0}
数据关系：R1={<ai-1,ai>|ai-1,ai∈D,i=2,…,n}
约定an端为栈顶，ai端为栈底
基本操作：
Push(&S,e)
初始条件：栈S已存在
操作结果：插入元素e为新的栈顶元素
Pop(&S,&e)
初始条件：栈S已存在且非空
操作结果：删除S的栈顶元素，并用e返回其值
}ADT Stack
3、各个模块的主要功能：
*Push(SC *s,char c)：把字符压栈
*Push(SF *s,float f)：把数值压栈
*Pop(SC *s)：把字符退栈
*Pop(SF *s)：把数值退栈
Operate(a,theta,b)：根据theta对a和b进行'+' 、'-' 、'*' 、'/' 、'^'操作
In(Test,*TestOp)：若Test为运算符则返回true，否则返回false
ReturnOpOrd(op,*TestOp)：若Test为运算符，则返回此运算符在数组中的下标
precede(Aop,Bop)：根据运算符优先级表返回Aop与Bop之间的优先级
EvaluateExpression(*MyExpression)：用算符优先法对算术表达式求值
完整的程序代码如下：
#include"stdio.h"#include"stdlib.h" #include"string.h" #include"math.h"#define true 1 #define false 0 #define OPSETSIZE 8 typedef int Status; unsigned char Prior[8][8] ={ // 运算符优先级表 // '+' '-' '*' '/' '(' ')' '#' '^' /*'+'*/'>','>','<','<','<','>','>','<', /*'-'*/'>','>','<','<','<','>','>','<', /*'*'*/'>','>','>','>','<','>','>','<', /*'/'*/'>','>','>','>','<','>','>','<', /*'('*/'<','<','<','<','<','=',' ','<', /*')'*/'>','>','>','>',' ','>','>','>', /*'#'*/'<','<','<','<','<',' ','=','<', /*'^'*/'>','>','>','>','<','>','>','>' }; typedef struct StackChar{char c; struct StackChar *next; }SC; //StackChar类型的结点SCtypedef struct StackFloat{float f; struct StackFloat *next; }SF; //StackFloat类型的结点SFSC *Push(SC *s,char c)//SC类型的指针Push，返回p{SC *p=(SC*)malloc(sizeof(SC)); p->c=c; p->next=s; return p; } SF *Push(SF *s,float f) //SF类型的指针Push，返回p{SF *p=(SF*)malloc(sizeof(SF)); p->f=f; p->next=s; return p; } SC *Pop(SC *s) //SC类型的指针Pop{SC *q=s; s=s->next; free(q); return s; } SF *Pop(SF *s)//SF类型的指针Pop{SF *q=s; s=s->next; free(q); return s; } float Operate(float a,unsigned char theta, float b)//计算函数Operate{switch(theta){case '+': return a+b; case '-': return a-b; case '*': return a*b; case '/': return a/b; case '^': return pow(a,b); default : return 0; } } char OPSET[OPSETSIZE]={'+','-','*','/','(',')','#','^'}; Status In(char Test,char *TestOp){int Find=false; for (int i=0; i< OPSETSIZE; i++){if(Test == TestOp[i])Find= true; } return Find; } Status ReturnOpOrd(char op,char *TestOp){ for(int i=0; i< OPSETSIZE; i++){if (op == TestOp[i])return i;}}char precede(char Aop, char Bop){ return Prior[ReturnOpOrd(Aop,OPSET)][ReturnOpOrd(Bop,OPSET)]; } float EvaluateExpression(char* MyExpression){ // 算术表达式求值的算符优先算法// 设OPTR和OPND分别为运算符栈和运算数栈，OP为运算符集合 SC *OPTR=NULL; // 运算符栈，字符元素 SF *OPND=NULL; // 运算数栈，实数元素 char TempData[20]; float Data,a,b; char theta,*c,Dr[]={'#','\0'}; OPTR=Push(OPTR,'#'); c=strcat(MyExpression,Dr); strcpy(TempData,"\0");//字符串拷贝函数 while (*c!= '#' || OPTR->c!='#'){ if (!In(*c, OPSET)){ Dr[0]=*c; strcat(TempData,Dr); //字符串连接函数 c++; if (In(*c, OPSET)){ Data=atof(TempData); //字符串转换函数(double) OPND=Push(OPND, Data); strcpy(TempData,"\0"); } } else // 不是运算符则进栈 {switch (precede(OPTR->c, *c)){case '<': // 栈顶元素优先级低 OPTR=Push(OPTR, *c); c++; break; case '=': // 脱括号并接收下一字符 OPTR=Pop(OPTR); c++; break; case '>': // 退栈并将运算结果入栈 theta=OPTR->c;OPTR=Pop(OPTR); b=OPND->f;OPND=Pop(OPND); a=OPND->f;OPND=Pop(OPND); OPND=Push(OPND, Operate(a, theta, b)); break; } //switch} } //while return OPND->f; } //EvaluateExpression int main(void){ char s[128];puts("请输入表达式:"); gets(s);puts("该表达式的值为:"); printf("%s\b=%g\n",s,EvaluateExpression(s));system("pause");return 0;}
测试结果如下：
