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<char> op;		//符号队列 
stack<double> 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;
}

NYOJ 35表达式求值,布布扣,bubuko.com

NYOJ 35表达式求值

原文：http://blog.csdn.net/user_longling/article/details/22758999