评价式1、实验主题1、案例分析2、案例实现3、算法步骤4、算法描述2、工具环境3、实验问题4、实验代码
一、实验主题1 .案例分析
这两个表达式都由“操作数”(operand )运算符(operator )和“边界符”(delimiter )组成，它们统称为单词。 一般而言，操作数可以是常数，或被描述为变量或常数的标识符； 算子可分为算术算子、关系算子、逻辑算子三类； 基本边界符号包括左右括号和表达式的结尾等。 为了简洁起见，这里只讨论简单算术表达式的评价问题。 这个公式只包含加、减、乘、除四种运算符。 读者很难把它推广到更一般的表达方式上。
以下，运算符和边界符统称为运算符。
我们知道算术四则运算遵循以下三条规则。
(1)先乘除，后加减
)2)从左往右
)3)前括号内、后括号外。
根据上述3个运算规则，在运算的各步骤中，任意2个连续的算子1和2之间的优先关系至多是以下3个关系中的任意一个。
1 2 1优先级低于2
1=2 1优先级与2相等
1 2 1优先顺序高于2
表3.1定义了运算符之间的这种优先关系。
根据规则(1)，先进行乘除运算，然后进行加减运算，所以有“”“*”。 「()/)； " * " '； //“”等。
根据规则(2)，运算服从左结合性。 在两个运算符相同的情况下，由于先出现的运算符的优先顺序高，所以“”“”； “-”“-”； “*”“*”； ()、)、)。
根据规则(3)，括号内的优先级高，-、*和/为1时的优先级都低于一千(“但高于”)。
表中的「()”=“)”表示左右括号相遇时，括号内的运算完成。 假设每个公式都以“#”开始，以“#”结束，以千实现。 因此，' #'=“#”表示整个表达式的评估已完成。 ' )“和()、)、和)”以及)、)、)、)、)、)、)、)、)、)、)、)之间没有优先级关系。 这可能是因为表达式不允许它们相继出现，在这种情况下发生了语法错误。 以下讨论假设输了的人的公式没有语法错误。
2 .情况下可以使用两个工作栈来实现算子优先算法。 一个称为OPTR，注册运算符； 另一个被称为OPND，登录操作数和运算结果。
3 .算法步骤1 .初始化optr堆栈和OPND堆栈，将表达式的起始符“#”推入optr堆栈。
2 .扫描表达式，阅读人的第一个字符ch，如果“#”或OPTR的堆栈顶部元素不是“#”，请重复以下操作：
如果ch不是运算符，则推入OPND堆栈，读取下一个字符ch；
如果ch是运算符，则根据OPTR堆栈顶部元素和ch的优先级的比较结果，进行不同的处理：
如果小，则将ch推入OPTR堆栈，读取下一个字符ch；
如果大于，则提取OPTR堆栈顶部的运算符，从OPND堆栈中提取两个个数，进行相应的运算，结果推入OPND堆栈；
如果等于，则OPTR的堆栈顶部元素为“(”，ch为“)”。 在这种情况下，将弹出OPTR堆栈顶部的“)”，括号匹配成功，相当于读取下一个字符ch。
3.OPND堆栈的顶级元素是表达式的计算结果，并返回此元素。
4 .算法描述char EvaluateExpression () /算术表达式评估的运算符优先算法，OPTR和OPND分别为运算符堆栈和操作数堆栈init堆栈(OPND )。 初始化OPND堆栈输入堆栈(OPTR )初始化OPTR堆栈推送(OPTR，' # ' )； //式的起始符“#”按在OPTR堆栈cinch上； 威尔(ch！=' # '||获取(optr )！='# ' )//表达式未扫描，或OPTR的堆栈顶部元素为' # '{if (！ 输入(ch ) )推(opnd，ch )； cin»ch； 如果//ch不是运算符，则将OPND堆栈elseswitch(precede(gettop(OPTR ) ch ) ) OPTR的堆栈顶部元素与ch的优先级进行比较(case':push ) OPTR，ch cinch； //当前字符ch推入OPTR堆栈，读取到下一个字符chbreak； case'':pop(optr，theta )； 弹出OPTR堆栈顶部的运算符pop(opnd，b )； pop(OPND，a )； OPND堆栈顶部的两个操作数push(opnd，operate(a，theta，b ) )；//将运算结果推入OPND堆栈break； case'=': //OPTR的堆栈顶部元素为'('且ch为') ) pop ) optr，x )； cinch； 弹出OPTR堆栈顶部的“”以读取下一个字符chbreak； (//开关)//whilereturngettop ) ) opnd； //OPND堆栈的顶级元素是表达式的评估结果}算法调用的三个函数需要读者自己补充完成。 在此，函数In是判定读入的字符ch是否是运算符，Precede是判定运算符堆栈的堆栈顶部要素和读入的运算符之间的优先关系的函数，Operate是进制
行二元运算的函数。 二、工具环境Window10操作系统，Microsoft Visual C++2010学习版 集成开发环境，C语言
三、实验问题另外需要特别说明的是，上述算法中的操作数只能是一位数，因为这里使用的OPND栈是字符栈，如果要进行多位数的运算，则需要将OPND栈改为数栈，读入的数字字符拼成数之后再入栈。 读者可以改进此算法，使之能完成多位数的运算。
四、实验代码 #include<stdio.h>#include<stdlib.h>#define MAXSIZE 100 //顺序栈存储空间的初始分配址#define OK 1#define ERROR 0#define OVERFLOW -2typedef int Status;typedef char SElemType;typedef struct{ char *base; //栈底指针 char *top; //栈顶指针 int stacksize; //栈可用的最大容量}SqStack;Status InitStack(SqStack *S);//构造一个空栈sStatus Push(SqStack *S,char e);//插入元素e为新的栈顶元素Status Pop(SqStack *S,char *e);//删除s的栈顶元素,用e返回其值SElemType GetTop(SqStack S);//返回s的栈顶元素,不修改栈顶指针Status In(char e);//判断读入字符是否为运算符SElemType Precede(char a,char b);//比较运算符的优先级，a为纵轴值，b为横轴值int Operate(int i,char theta,int j);//计算a(theta)b结果char EvaluateExpression();//算术表达式求值的算符优先算法，设OPTR和OPND分别为运算符栈和操作数栈int main(){ printf("请输入算术表达式,并以#结束(操作数只能是一位数)："); printf("表达式结果是：%d",EvaluateExpression()); return 0;}Status InitStack(SqStack *S){//构造一个空栈sS->base=(char *)malloc(MAXSIZE*sizeof(char));//为顺序栈动态分配一个最大容量为MAXSIZE的数组空间 if(!S->base) exit(OVERFLOW); //存储分配失败 S->top=S->base; //top初始为base，空栈 S->stacksize=MAXSIZE; //stacksize置为栈的最大容量MAXSIZEreturn OK;}Status Push(SqStack *S,char e){//插入元素e为新的栈顶元素if(S->top-S->base==S->stacksize) return ERROR; //栈满 *S->top++=e; //元素e压入栈顶，栈顶指针加1 return OK;}Status Pop(SqStack *S,char *e){//删除s的栈顶元素，用e返回其值if(S->top==S->base) return ERROR; //栈空 *e=*--S->top; //栈顶指针减1，将栈顶元素赋给e return OK;} SElemType GetTop(SqStack S){//返回s的栈顶元素，不修改栈顶指针if(S.top!=S.base) //栈非空 return *(S.top-1); //返回栈顶元素的值，栈顶指针不变}Status In(char e) {//判断读入字符是否为运算符if(e=='+'||e=='-'||e=='*'||e=='/'||e=='('||e==')'||e=='#') return OK;//是 else return ERROR;//不是}SElemType Precede(char a,char b) {//比较运算符的优先级，a为纵轴值，b为横轴值 char f; if(a=='+'||a=='-') { if(b=='+'||b=='-'||b==')'||b=='#') f='>'; else if(b=='*'||b=='/'||b=='(') f='<'; } else if(a=='*'||a=='/') { if(b=='+'||b=='-'||b=='*'||b=='/'||b==')'||b=='#') f='>'; else if(b=='(') f='<'; } else if(a=='(') { if(b=='+'||b=='-'||b=='*'||b=='/'||b=='(') f='<'; else if(b==')') f='='; } else if(a==')') { if(b=='+'||b=='-'||b=='*'||b=='/'||b==')'||b=='#') f='>'; } else if(a=='#') { if(b=='+'||b=='-'||b=='*'||b=='/'||b=='(') f='<'; else if(b=='#') f='='; } return f;}int Operate(int i,char theta,int j) {//计算a(theta)b结果 int result; switch(theta) { case '+': result = i + j; break; case '-': result = i - j; break; case '*': result = i * j; break; case '/': result = i / j; break; } return result;}char EvaluateExpression(){//算术表达式求值的算符优先算法，设OPTR和OPND分别为运算符栈和操作数栈 SqStack OPND,OPTR; int ch; //把读入的字符转换为整数型，即ASCII表值 char a,b,theta,x; //ch为当前读入字符, theta为运算符，x仅仅只是变量寄存弹出值，对计算表达式无影响 InitStack(&OPND); //初始化OPND栈，寄存操作数和运算结果 InitStack(&OPTR); //初始化OPTR栈，寄存运算符 Push(&OPTR,'#');ch=getchar(); while(ch!='#'||GetTop(OPTR)!='#') {printf(" %cn",ch);if(!In(ch))//ch不是运算符则进OPND栈 {ch=ch-48;//数字字符转换为对应整数Push(&OPND,ch);ch=getchar(); } else { switch(Precede(GetTop(OPTR),ch)) {//优先级选择 case '<': Push(&OPTR,ch);ch=getchar(); break; case '>': Pop(&OPTR,&theta); Pop(&OPND,&b); Pop(&OPND,&a); Push(&OPND,Operate(a,theta,b)); break; case '=': Pop(&OPTR,&x);ch=getchar(); break; } } }return GetTop(OPND);}