NYOJ--郁闷的C小加（三）

我不是女神ヾ 2022-08-26 15:17 137阅读 0赞

## 郁闷的C小加（三） ##

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

难度： 4

描述

聪明的你帮助C小加解决了中缀表达式到后缀表达式的转换（详情请参考“郁闷的C小加（一）”），C小加很高兴。但C小加是个爱思考的人，他又想通过这种方法计算一个表达式的值。即先把表达式转换为前缀和后缀表达式，再求值。这时又要考虑操作数是小数和多位数的情况。

输入

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

输出

对于每组测试数据输出结果包括三行，先输出转换后的前缀和后缀表达式，再输出计算结果，结果保留两位小数。

样例输入

2
    1+2=
    (19+21)*3-4/5=

样例输出

+ 1 2 =
    1 2 + =
    3.00
    - * + 19 21 3 / 4 5 =
    19 21 + 3 * 4 5 / - =
    119.20

解析：给出中缀表达式输出前缀表达式和后缀表达式以及求表达式的值，也算是表达式中比较全的，最近一直在做表达式，就顺便把这个也给AC了，代码那是相当长。。。把前面零零星星写的又重写写了一遍，不过思想掌握了，写代码还是比较快的哈！

#include <iostream>
    #include <algorithm>
    #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;
    //定义存放运算符的栈
    stack<char> op;
    stack<double> numstack;
    //定义运算符的优先级
    int priority(char ch)
    {
    	switch(ch)
    	{
    	case '+':
    	case '-':
    		return 1;
    	case '*':
    	case '/':
    		return 2;
    	default:
    		return 0;
    	}
    }
    //运算符运算的实现
    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 isDigit(char ch)
    {
    	if(ch=='+'||ch=='-'||ch=='*'||ch=='/')
    		return 1;
    	else
    		return 0;
    }
    //输出前缀表达式
    void PrintPrimExpression(const string &str)
    {
    	//存储前缀表达式的字符串
    	string res("= ");
    	//逆序检查表达式来求前缀表达式
    	for(int i=str.length()-2;i>=0;--i)
    	{
    		if(str[i]==')')
    		{//当前字符是右括号时
    			op.push(str[i]);
    		}else if(str[i]=='(')
    		{//当前字符是左括号
    			while(op.top()!=')')
    			{
    				res+=op.top();
    				res+=' ';
    				op.pop();
    			}
    			//将右括号弹出来
    			op.pop();
    		}else if(isDigit(str[i]))
    		{//如果是运算符的话
    			while(!op.empty()&&priority(op.top())>priority(str[i]))
    			{
    				res+=op.top();
    				res+=' ';
    				op.pop();
    			}
    			op.push(str[i]);
    		}else{
    			//当前字符是数字或者是小数点等
    			res+=str[i];
    			//判断当前res中是否是一个独立的数
    			if((i>0&&(isDigit(str[i-1])||str[i-1]=='('))||(i==0))
    			{
    				//如果前面是一个独立的数则加上空格
    				res+=' ';
    			}
    		}
    	}
    	//当符号栈不空时
    	while(!op.empty())
    	{
    		res+=op.top();
    		res+=' ';
    		op.pop();
    	}
    	//去掉res字符串中最后一个空格然后逆转
    	reverse(res.begin(),res.end()-1);
    	cout << res << endl;
    }
    //输出后缀表达式及表达式的值
    void PrintExpressionValue(const string &str)
    {
    	//存放后缀表达式的字符串
    	string res("");
    	string temp("");
    	for(int i=0;i<str.length()-1;++i)
    	{
    		if(str[i]=='(')
    		{
    			op.push(str[i]);
    		}else if(str[i]==')')
    		{
    			while(op.top()!='(')
    			{
    				double t1=numstack.top();
    				numstack.pop();
    				double t2=numstack.top();
    				numstack.pop();
    				double result=compute(t2,t1,op.top());
    				res+=op.top();
    				res+=' ';
    				op.pop();
    				numstack.push(result);
    			}
    			op.pop();
    		}else if(isDigit(str[i]))
    		{
    			//比较运算符的优先级
    			while(!op.empty()&&priority(op.top())>=priority(str[i]))
    			{
    				double t1=numstack.top();
    				numstack.pop();
    				double t2=numstack.top();
    				numstack.pop();
    				double result=compute(t2,t1,op.top());
    				res+=op.top();
    				res+=' ';
    				op.pop();
    				numstack.push(result);
    			}
    			op.push(str[i]);
    		}else{
    			//当为数字或者小数点或者等号时
    			res+=str[i];
    			temp+=str[i];
    			//判断temp中是否为一个独立的数
    			if(i<str.length()-1&&(str[i+1]=='='||str[i+1]==')'||isDigit(str[i+1])))
    			{
    				res+=' ';
    				numstack.push(atof(temp.c_str()));
    				//重置temp
    				temp.clear();
    			}
    		}
    	}
    	//当操作符栈不空时
    	while(!op.empty())
    	{
    		double t1=numstack.top();
    		numstack.pop();
    		double t2=numstack.top();
    		numstack.pop();
    		double result=compute(t2,t1,op.top());
    		res+=op.top();
    		res+=' ';
    		op.pop();
    		numstack.push(result);
    	}
    	res+='=';
    	cout << res << endl;
    	printf("%.2f\n",numstack.top());
    	//清空操作数栈
    	while(!numstack.empty())
    	{
    		numstack.pop();
    	}
    }
    int main()
    {
    	int T;
    	cin >> T;
    	while(T--)
    	{
    		string str;
    		cin >> str;
    		//输出前缀表达式
    		PrintPrimExpression(str);
    		//输出后缀表达式并同时计算表达式的值
    		PrintExpressionValue(str);
    	}
    	return 0;
    }