NYOJ--前缀式计算

落日映苍穹つ 2022-08-26 15:13 71阅读 0赞

## 前缀式计算 ##

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

难度： 3

描述

先说明一下什么是中缀式：

如2+(3+4)\*5这种我们最常见的式子就是中缀式。

而把中缀式按运算顺序加上括号就是：(2+((3+4)\*5))

然后把运算符写到括号前面就是+(2 \*( +(3 4) 5) )

把括号去掉就是：+ 2 \* + 3 4 5

最后这个式子就是该表达式的前缀表示。

给你一个前缀表达式，请你计算出该前缀式的值。

比如：

\+ 2 \* + 3 4 5的值就是 37

输入

有多组测试数据，每组测试数据占一行，任意两个操作符之间，任意两个操作数之间，操作数与操作符之间都有一个空格。输入的两个操作数可能是小数，数据保证输入的数都是正数，并且都小于10，操作数数目不超过500。  
以EOF为输入结束的标志。

输出

对每组数据，输出该前缀表达式的值。输出结果保留两位小数。

样例输入

+ 2 * + 3 4 5
    + 5.1 / 3 7

样例输出

37.00
    5.53

来源

[经典题目][Link 1]

解析：前面一直在研究中缀表达式和后缀表达式，这次做做前缀表达式，不过思想还是一样的，逆序着判断几种情况做不同的操作，存入操作数栈，然后将操作数栈顶两元素与当前遇到的操作符计算即可，废话不说直接上代码，代码注释我觉得还是很详细的哈！

#include <iostream>
    #include <stack>
    #include <string>
    #include <stdio.h>
    #include <stdlib.h>
    #include <algorithm>
    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 isDigit(char ch)
    {
    	if(ch=='+'||ch=='-'||ch=='*'||ch=='/')
    	{
    		return 1;
    	}else{
    		return 0;
    	}
    }
    int main()
    {
    	string str;
    	stack<double> numstack;
    	//读取一行字符串
    	while(getline(cin , str))
    	{
    		string res;
    		for(int i=str.length()-1;i>=0;--i)
    		{//将操作数入栈
    			if(isDigit(str[i]))
    			{//如果当前字符是操作符
    				//从操作数栈中栈顶提取两个数进行运算
    				double t1=numstack.top();
    				numstack.pop();
    				double t2=numstack.top();
    				numstack.pop();
    				double result=compute(t1,t2,str[i]);
    				numstack.push(result);
    			}else if(str[i]==' ')
    			{//当前字符是空格不做处理
    
    			}else{
    				//当前字符是数字或者小数点
    				res+=str[i];
    				//判断当前res中存储的字符串是否为一个单独的数
    				if((i>0&&str[i-1]==' ')||(i==0))
    				{//如果前一个字符是空格的话则是一个单独的数
    					reverse(res.begin(),res.end());
    					//转换为double类型的数
    					double temp=atof(res.c_str());
    					numstack.push(temp);
    					//重置res字符串
    					res.clear();
    				}
    			}
    		}
    		printf("%.2f\n",numstack.top());
    		//清空栈
    		while(!numstack.empty())
    		{
    			numstack.pop();
    		}
    	}
    	return 0;
    }

[Link 1]: http://acm.nyist.edu.cn/JudgeOnline/search_result.php?source=%E7%BB%8F%E5%85%B8%E9%A2%98%E7%9B%AE