1345 - 算法3-4：表达式求值
时间限制 : 1 秒
内存限制 : 32 MB
算数四则运算的规则是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
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; }
Java解答
import java.io.*; import java.util.Stack; public class Main { public static Boolean gogo(char a,char b) { if(a=='('||b=='(') return false; else if(a=='*'||a=='/'||b=='+'||b=='-'||b==')') return true; else return false; } public static void main(String[] args) throws IOException { BufferedReader cin = new BufferedReader(new InputStreamReader(System.in)); String s; char t; int a,b; Stack<Character> p=new Stack<Character>(); Stack<Integer> d=new Stack<Integer>(); while((s=cin.readLine())!=null) //cin.ready() { for(int i=0;i<s.length()&&s.charAt(i)!='#';i++) { t=s.charAt(i); if(t=='+'||t=='-'||t=='*'||t=='/'||t=='('||t==')') { while(p.empty()!=true) { if(t==')'&&p.peek()=='(') { if(i<s.length()-1&&s.charAt(i+1)!='#') { i++; t=s.charAt(i); } p.pop(); } if(p.empty()!=true&&gogo(p.peek(),t)) { b=d.pop(); a=d.pop(); if(p.peek()=='+') { a=a+b; } else if(p.peek()=='-') { a=a-b; } else if(p.peek()=='*') { a=a*b; } else if(p.peek()=='/') { a=a/b; } d.push(a); p.pop(); } else break; } if(t!=')') p.push(t); } else { a=t-'0'; for(int j=i+1;j<s.length();j++) { if(Character.isDigit(s.charAt(j))) { a=a*10+(s.charAt(j)-'0'); i++; } else { i=j-1; break; } } d.push(a); } } while(p.empty()!=true) { b=d.pop(); a=d.pop(); if(p.peek()=='+') { a=a+b; } else if(p.peek()=='-') { a=a-b; } else if(p.peek()=='*') { a=a*b; } else if(p.peek()=='/') { a=a/b; } d.push(a); p.pop(); } System.out.println(d.peek()); p.clear(); d.clear(); } cin.close(); } }
Python解答
while True: try: print(eval(raw_input()[:-1])) except EOFError: break