1345 - 算法3-4：表达式求值
算数四则运算的规则是1）先乘除，后加减；2）从左算到右；3）先括号内，后括号外。
由此，算式4+2*3-10/5的计算顺序为4+2*3-10/5=4+6-10/5=4+6-2=8。
给定一个以“#”作为结束符的算式，求出算式的结果。
给出严蔚敏《数据结构（C语言）》中的一段算法描述以作参考：
图1：表达式求值算法
<img width="524" height="361" alt="" src="http://tk.hustoj.com:80/upload/pimg1743_2.jpg" />
图2：表达式求值算法（续）
<img width="481" height="236" alt="" src="http://tk.hustoj.com:80/upload/pimg1743_3.jpg" />
<span style="font-size:10.5pt;">图</span><span style="font-size:10.5pt;">3</span><span style="font-size:10.5pt;">：表达式求值算法（续）</span>
题目输入
以“#”结尾的表达式，运算数为正整数。每个表达式占一行。
题目输出
输出表达式运算的结果。
输入/输出样例
题目输入
4+2*3-10/5# 3*(7-2)# 2*3/2#
题目输出
8 15 3
提示
提示：使用栈来解决本题，很多人都会想到。但怎样建栈，却带来了问题。同样，严书上的代码实际上也给大家带来了问题。看过严书光盘中代码的人应该知道，代码中使用了两个栈，一个是存储运算符的，类型为char；另一个存储运算数，类型为float。而操作两个栈的函数都一样。要知道，除非像C++中使用泛型，C语言中却基本不能实现这样的操作。所以在C语言环境中需要将这两个栈结合在一起。由于char与int有种特别的联系，可以使用int来代替char存储运算符。总结：注意灵活运用栈，要是能够学习C++使用template就更好了。可以模拟STL了。
C语言解答
#include <stdio.h> #include <stdlib.h> #include <string.h> unsigned char prior[7][7]={ {'>','>','<','<','<','>','>'}, {'>','>','<','<','<','>','>'}, {'>','>','>','>','<','>','>'}, {'>','>','>','>','<','>','>'}, {'<','<','<','<','<','=',' '}, {'>','>','>','>',' ','>','>'}, {'<','<','<','<','<',' ','='} }; char opset[7]={'+','-','*','/','(',')','#'}; int is_op(char c); char precede(char a,char b); int getIndex(char c); int operate(int a,char op,int b); int main() { char expression[256]; int evaluate=0; while(scanf("%s",expression)==1) { evaluate=evaluateExpression(expression); printf("%d\n",evaluate); } return 0; } int evaluateExpression(char *expression) { char optr[256]; int opnd[256]; int top1,top2; char tempData[20]; int data,a,b; char *c,dr[2]; int x,i; char op; top1=top2=-1; optr[++top1]='#'; c=expression; strcpy(tempData,"\0"); while(*c!='#'||optr[top1]!='#') { if(!is_op(*c)) { dr[0]=*c; dr[1]='\0'; strcat(tempData,dr); c++; if(is_op(*c)) { data=atoi(tempData); opnd[++top2]=data; strcpy(tempData,"\0"); } } else { switch(precede(optr[top1],*c)) { case '<': optr[++top1]=*c; c++; break; case '=': top1--; c++; case '>': op=optr[top1--]; b=opnd[top2--]; a=opnd[top2--]; opnd[++top2]=operate(a,op,b); break; } } } return opnd[top2]; } int is_op(char c) { int i; for(i=0;i<7;i++) if(c==opset[i]) return 1; return 0; } char precede(char a,char b) { int i,j; i=getIndex(a); j=getIndex(b); return prior[i][j]; } int getIndex(char c) { int i; for(i=0;i<7;i++) if(c==opset[i]) return i; } int operate(int a,char op,int b) { int value; switch(op) { case '+': value=a+b; break; case '-': value=a-b; break; case '*': value=a*b; break; case '/': value=a/b; break; } return value; }
C++解答
#include <stdio.h> #include <stdlib.h> #include <string.h> #define STACK_INIT_SIZE 100 // 存储空间初始分配量 #define STACKINCREMENT 10 // 存储空间分配增量 typedef int Status; #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define OVERFLOW 0 // 栈分配溢出 #define OPSETSIZE 7 // 表3.1 算符间的优先关系 unsigned char Prior[7][7] = { { '>', '>', '<', '<', '<', '>', '>' }, { '>', '>', '<', '<', '<', '>', '>' }, { '>', '>', '>', '>', '<', '>', '>' }, { '>', '>', '>', '>', '<', '>', '>' }, { '<', '<', '<', '<', '<', '=', ' ' }, { '>', '>', '>', '>', ' ', '>', '>' }, { '<', '<', '<', '<', '<', ' ', '=' } }; char OPSET[OPSETSIZE]= { '+', '-', '*', '/', '(', ')', '#' }; typedef int SElemType; typedef struct { SElemType * base; // 在栈构造之前和销毁之后，base的值为NULL SElemType * top; // 栈顶指针 int stacksize; // 当前已分配的存储空间，以元素为单位 } SqStack; Status InitStack(SqStack &S) { // 构造一个空栈 S.base = (SElemType *) malloc(STACK_INIT_SIZE * sizeof(SElemType)); if (!S.base) exit(OVERFLOW); // 存储分配失败 S.top = S.base; S.stacksize = STACK_INIT_SIZE; return OK; }// InitStack SElemType GetTop(SqStack S) { return *(S.top - 1); }// GetTop Status Push(SqStack &S, SElemType e) { // 插入元素 e 为新的栈顶元素 if (S.top - S.base >= S.stacksize) { //栈满，追加存储空间 S.base = (SElemType *) realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(SElemType)); if (!S.base) exit(OVERFLOW); // 存储分配失败 S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; } *S.top++ = e; return OK; } // Push Status Pop(SqStack &S, SElemType &e) { // 若栈不为空，则删除 S 的栈顶元素，用 e 返回其值，并返回 OK；否则返回 ERROR if (S.top == S.base) return ERROR; e = *--S.top; return OK; } // Pop Status StackEmpty(SqStack S) { // 若栈 S 为空栈，则返回 TRUE，否则返回 FALSE return S.top == S.base; } // StackEmpty void ClearStack(SqStack &S) { // 将栈 S 清空 S.top = S.base; } // ClearStack void DestroyStack(SqStack &S) { // 销毁整个栈 while (S.top != S.base) { // 释放栈中元素的空间 free(--S.top); } S.top = S.base = NULL; } // DestroyStack int Operate(int a, unsigned char theta, int b) { switch (theta) { case '+': return a + b; case '-': return a - b; case '*': return a * b; case '/': return a / b; default: return 0; } } Status In(char Test, char* TestOp) { int Find = 0; int i; for (i = 0; i < OPSETSIZE; i++) { if (Test == TestOp[i]) Find = 1; } return Find; } int ReturnOpOrd(char op, char* TestOp) { int i; for (i = 0; i < OPSETSIZE; i++) { if (op == TestOp[i]) return i; } return 0; } char precede(char Aop, char Bop) { return Prior[ReturnOpOrd(Aop, OPSET)][ReturnOpOrd(Bop, OPSET)]; } int EvaluateExpression(char* MyExpression) { // 算法3.4 // 算术表达式求值的算符优先算法。 // 设OPTR和OPND分别为运算符栈和运算数栈，OP为运算符集合。 SqStack OPTR; // 运算符栈，字符元素 SqStack OPND; // 运算数栈，实数元素 char TempData[20]; int Data, a, b; char *c, Dr[2]; int x, theta; InitStack(OPTR); Push(OPTR, '#'); InitStack(OPND); c = MyExpression; strcpy(TempData, "\0"); while (*c != '#' || GetTop(OPTR) != '#') { if (!In(*c, OPSET)) { // 不是运算符则进栈 Dr[0] = *c; Dr[1] = '\0'; strcat(TempData, Dr); c++; if (In(*c, OPSET)) { Data = atoi(TempData); Push(OPND, Data); strcpy(TempData, "\0"); } } else { switch (precede(GetTop(OPTR), *c)) { case '<': // 栈顶元素优先权低 Push(OPTR, *c); c++; break; case '=': // 脱括号并接收下一字符 Pop(OPTR, x); c++; break; case '>': // 退栈并将运算结果入栈 Pop(OPTR, theta); Pop(OPND, b); Pop(OPND, a); Push(OPND, Operate(a, theta, b)); break; } // switch } } // while return GetTop(OPND); } // EvaluateExpression int main(){ char MyExpression[100]; // 获得表达式字符串 while(gets(MyExpression) && strlen(MyExpression)){ printf("%d\n", EvaluateExpression(MyExpression)); } return 0; }
提示
提示：
使用栈来解决本题，很多人都会想到。但怎样建栈，却带来了问题。同样，严书上的代码实际上也给大家带来了问题。看过严书光盘中代码的人应该知道，代码中使用了两个栈，一个是存储运算符的，类型为char；另一个存储运算数，类型为float。而操作两个栈的函数都一样。要知道，除非像C++中使用泛型，C语言中却基本不能实现这样的操作。所以在C语言环境中需要将这两个栈结合在一起。由于char与int有种特别的联系，可以使用int来代替char存储运算符。
总结：
注意灵活运用栈，要是能够学习C++使用template就更好了。可以模拟STL了。