NYOJ 35表达式求值

表达式求值

描述 ACM队的mdd想做一个计算器，但是，他要做的不仅仅是一计算一个A+B的计算器，他想实现随便输入一个表达式都能求出它的值的计算器，现在请你帮助他来实现这个计算器吧。
比如输入：“1+2/4=”，程序就输出1.50（结果保留两位小数）

输入第一行输入一个整数n，共有n组测试数据（n<10)。
每组测试数据只有一行，是一个长度不超过1000的字符串，表示这个运算式，每个运算式都是以“=”结束。这个表达式里只包含+-*/与小括号这几种符号。其中小括号可以嵌套使用。数据保证输入的操作数中不会出现负数。
数据保证除数不会为0输出每组都输出该组运算式的运算结果，输出结果保留两位小数。样例输入

2
1.000+2/4=
((1+2)*5+1)/4=

样例输出

1.50
4.00

/*
		表达式计算思路：从左到右遍历中缀表达式中的每个数字和符号，
	若是数字则直接压入数据栈中，若是符号（左括号直接入符号栈），则
	判断其与栈顶符号的优先级，是右括号或优先级低于栈顶符号，则栈
	（符号栈即数据栈）中的元素依次出栈并计算，直到遇到左括号或栈
	顶元素优先级小于该符号压入符号栈为止，最后符号栈依次出栈计算
	直至符号为空。 
*/ 

#include "stdio.h"
#include "ctype.h"
#include "stack"
#define maxn 1000+10

using namespace std;

char buf[maxn];
stack
    
      op;		//符号队列 
stack
     
       n; //得到操作符的优先级 int getValue(char c){ if('('==c) return 0; if('+'==c || '-'==c) return 1; if('*'==c || '/'==c) return 2; } double calc(double a,double b,char c) { // printf("出栈操作：%f %c %f \n",a,c,b); switch(c){ case '+': return (a+b); case '-': return (a-b); case '*': return (a*b); case '/': return (a/b); } } //操作符出栈，即进行计算一次 void pull() { double a,b; if(n.size()>1 && !op.empty()){ b=n.top(); n.pop(); a=n.top(); n.pop(); n.push(calc(a,b,op.top())); //printf("%d:出栈结果入栈！\n",n.size()); op.pop();// printf("符号：%d 数字: %d 出栈完毕！\n",op.size(),n.size()); } } int main() { int N,i; double d; char c; scanf("%d",&N); while(N--){ scanf("%s",buf); i=0; while(1){ if(isalnum(buf[i])){ sscanf(buf+i,"%lf",&d); n.push(d);// printf("%d:数字入栈：%lf\n",n.size(),d); while(isalnum(buf[i]) || '.'==buf[i]) i++; } c=buf[i++]; if('='==c || '\0'==c) break; if('('==c){ op.push(c); // printf("(入栈\n"); }else if(')'==c){ while(!op.empty()){ if('('==op.top()) {op.pop(); break; } pull(); } }else{ //注意先后顺序，不为空才能进行op.top()操作 while( !op.empty() && getValue(c)<=getValue(op.top())) pull(); op.push(c); //printf("%d:符号入栈：%c \n",op.size(),c); } } while(!op.empty()) pull(); printf("%.2lf\n",n.top()); while(!n.empty()) n.pop(); } return 0; }