NYOJ--表达式求值

谁践踏了优雅 2022-08-26 15:12 182阅读 0赞

## 表达式求值 ##

时间限制： 3000 ms  |  内存限制： 65535 KB

难度： 4

描述

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

来源

[数据结构课本例题改进][Link 1]

解析：这又是上一篇博客中中缀表达式-->后缀表达式的加强版，不仅数字的位数是多位而且要计算出该中缀表达式的值，很多人都采用栈来做，符号栈和操作数栈，感觉那样会很麻烦，当然栈是离不了的，首先将中缀表达式转换为后缀表达式，然后将运算符栈的栈顶元素和操作数站的栈顶两元素进行计算即可，如果以前写过中缀表达式转换为后缀表达式的代码，那这道应该也没什么问题了，可惜自己有点水，在判断输入的表达式中，怎么去判断当前是否是一个单独的数上wa了几次，另外在字符串转换double类型的时候可以直接利用函数atof()，唉……还是代码写的太少哈！

贴一下自己AC的代码

#include <iostream>
    #include <string>
    #include <stack>
    #include <stdio.h>
    #include <stdlib.h>
    using std::endl;
    using std::cin;
    using std::cout;
    using std::string;
    using std::stack;
    //实现两个数的加减乘除
    double compute(double a,double b,char ch)
    {
    	switch(ch)
    	{
    	case '+':
    		return a+b;
    	case '-':
    		return a-b;
    	case '*':
    		return a*b;
    	case '/':
    		return a/b;
    	}
    }
    //定义运算符的优先级
    int priority(char ch)
    {
    	int num;
    	switch(ch)
    	{
    	case '+':
    	case '-':
    		num=1;
    		break;
    	case '*':
    	case '/':
    		num=2;
    		break;
    	case '(':
    	case ')':
    		num=0;
    		break;
    	default:
    		num=-1;
    		break;
    	}
    	return num;
    }
    int main()
    {
    	int T;
    	cin >> T;
    	//定义保存运算符的栈
    	stack<char> op;
    	//定义保存每个double数值的栈
    	stack<double> numstack;
    	op.push('#');
    	while(T--)
    	{
    		string str1,str2;
    		double result=0;
    		cin >> str1;
    		//将中缀表达式转换为后缀表达式
    		for(int i=0;i<str1.length()-1;++i)
    		{//扫描一遍输入的字符串进行转换
    			if(str1[i]=='(')
    			{
    				op.push(str1[i]);
    			}else if(str1[i]==')')
    			{
    				//遇到(则停止弹出
    				while(op.top()!='(')
    				{
    					//出栈之前进行计算,从存放double栈中提取栈顶两数与op栈顶操作符进行运算
    					double t1=numstack.top();
    					numstack.pop();
    					double t2=numstack.top();
    					numstack.pop();
    					result=compute(t2,t1,op.top());
    					numstack.push(result);
    					//将栈顶的运算符弹出
    					op.pop();
    				}
    				//将左括号从栈中弹出
    				op.pop();
    			}else if(str1[i]=='+'||str1[i]=='-'||str1[i]=='*'||str1[i]=='/')
    			{
    				//如果当前的操作符比栈顶的操作符优先级大的话，则将当前操作符压入栈
    				if(priority(str1[i])>priority(op.top()))
    				{
    					op.push(str1[i]);
    				}else{
    					//当前运算符优先级小，则将栈中运算符优先级大于等于当前的都从栈中弹出来
    					while(priority(op.top())>=priority(str1[i]))
    					{
    						//出栈之前进行计算,从存放double栈中提取栈顶两数与op栈顶操作符进行运算
    						double t1=numstack.top();
    						numstack.pop();
    						double t2=numstack.top();
    						numstack.pop();
    						result=compute(t2,t1,op.top());
    						numstack.push(result);
    						//将栈顶的运算符弹出
    						op.pop();
    					}
    					//然后再压入当前的运算符
    					op.push(str1[i]);
    				}
    			}else{
    				str2+=str1[i];
    				//判断当前str2中存储的是否是一个单独的数
    				if(i<str1.length()-1&&(str1[i+1]=='='||str1[i+1]=='+'||str1[i+1]=='-'||str1[i+1]=='*'||str1[i+1]=='/'||str1[i+1]==')'))
    				{//如果当前字符串是一个单独的数则转换为double类型存放到操作数栈中
    					double temp=atof(str2.c_str());
    					//进行保存
    					numstack.push(temp);
    					//str2进行重置清空
    					str2.clear();
    				}
    			}
    		}
    		//如果此时符号栈仍不为空则全部出栈
    		while(op.top()!='#')
    		{
    			//出栈之前进行计算,从存放double栈中提取栈顶两数与op栈顶操作符进行运算
    			double t1=numstack.top();
    			numstack.pop();
    			double t2=numstack.top();
    			numstack.pop();
    			result=compute(t2,t1,op.top());
    			numstack.push(result);
    			//将栈顶的运算符弹出
    			op.pop();
    		}
    		printf("%.2f\n",numstack.top());
    		//将栈清空
    		while(!numstack.empty())
    		{
    			numstack.pop();
    		}
    	}
    }

[Link 1]: http://acm.nyist.edu.cn/JudgeOnline/search_result.php?source=%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E8%AF%BE%E6%9C%AC%E4%BE%8B%E9%A2%98%E6%94%B9%E8%BF%9B