中缀式转后缀表达式 -NYOJ 题目267郁闷的C小加(二)

郁闷的C小加(二)

时间限制:1000 ms  |  内存限制:65535 KB
难度:4
描述

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

输入
第一行输入一个整数T,共有T组测试数据(T<10)。
每组测试数据只有一行,是一个长度不超过1000的字符串,表示这个运算式,每个运算式都是以“=”结束。这个表达式里只包含+-*/与小括号这几种符号。其中小括号可以嵌套使用。数据保证输入的操作数中不会出现负数并且小于1000000。
数据保证除数不会为0。
输出
对于每组测试数据输出结果包括两行,先输出转换后的后缀表达式,再输出计算结果,结果保留两位小数。两组测试数据之间用一个空行隔开。
样例输入
21+2=
(19+21)*3-4/5=
样例输出
12+=
3.00
 
1921+3*45/-=
119.20

本题用到的技巧:

1.#include<stack> 其中第一好了栈以及其操作,简化了代码

2.atof函数

功 能: 把字符串转换成浮点数
表头文件 #include <stdlib.h>
名字来源:ascii to floating point numbers 的缩写
用 法: double atof(const char *nptr);
程序例:
#include <stdlib.h> 
#include <stdio.h> 
int main() 
{   
	float f;   
 	char *str = "12345.67";   
	f = atof(str);   
	printf("string = %s float = %f\n", str, f);   
	return 0; 
} 


相关函数 atoiatolstrtodstrtolstrtoul

3.sscanf函数 提取一个字符串中的各个类型的数据,分类提取很方便

 

WA了数十次,一开始我以为是情况没考虑完,停了几天后忽然想到是不是后缀表达式煤球正确

然后找了 中缀表达式转后缀的方法:

1)规则

中缀表达式a + b*c + (d * e + f) * g,其转换成后缀表达式则为a b c * + d e * f  + g * +。

转换过程需要用到栈,具体过程如下:

1)如果遇到操作数,我们就直接将其输出。

2)如果遇到操作符,则我们将其放入到栈中,遇到左括号时我们也将其放入栈中。

3)如果遇到一个右括号,则将栈元素弹出,将弹出的操作符输出直到遇到左括号为止。注意,左括号只弹出并不输出。

4)如果遇到任何其他的操作符,如(“+”, “*”,“(”)等,从栈中弹出元素直到遇到发现更低优先级的元素(或者栈为空)为止。弹出完这些元素后,才将遇到的操作符压入到栈中。有一点需要注意,只有在遇到" ) "的情况下我们才弹出" ( ",其他情况我们都不会弹出" ( "。也就是说这种操作," + "的优先级最低," ( "优先级最高。

5)如果我们读到了输入的末尾,则将栈中所有元素依次弹出。

 

2)实例

规则很多,还是用实例比较容易说清楚整个过程。以上面的转换为例,输入为a + b * c + (d * e + f)*g,处理过程如下:

1)首先读到a,直接输出。

2)读到“+”,将其放入到栈中。

3)读到b,直接输出。

此时栈和输出的情况如下:

 

4)读到“*”,因为栈顶元素"+"优先级比" * " 低,所以将" * "直接压入栈中。

5)读到c,直接输出。

此时栈和输出情况如下:

 

6)读到" + ",因为栈顶元素" * "的优先级比它高,所以弹出" * "并输出, 同理,栈中下一个元素" + "优先级与读到的操作符" + "一样,所以也要弹出并输出。然后再将读到的" + "压入栈中。

此时栈和输出情况如下:

 

7)下一个读到的为"(",它优先级最高,所以直接放入到栈中。

8)读到d,将其直接输出。

此时栈和输出情况如下:

 

9)读到" * ",由于只有遇到" ) "的时候左括号"("才会弹出,所以" * "直接压入栈中。

10)读到e,直接输出。

此时栈和输出情况如下:

 

11)读到" + ",弹出" * "并输出,然后将"+"压入栈中。

12)读到f,直接输出。

此时栈和输出情况:

 

 

13)接下来读到“)”,则直接将栈中元素弹出并输出直到遇到"("为止。这里右括号前只有一个操作符"+"被弹出并输出。

 

14)读到" * ",压入栈中。读到g,直接输出。

 

15)此时输入数据已经读到末尾,栈中还有两个操作符“*”和" + ",直接弹出并输出。

至此整个转换过程完成。程序实现代码后续再补充了。

 

 3)转换的另一种方法

1)先按照运算符的优先级对中缀表达式加括号,变成( ( a+(b*c) ) + ( ((d*e)+f) *g ) )

2)将运算符移到括号的后面,变成((a(bc)*)+(((de)*f)+g)*)+

3)去掉括号,得到abc*+de*f+g*+

 

计算就好说了,根据后缀表达式,遇到运算符则弹出两个操作数,计算后压栈,最后栈顶元素为计算结果

代码:

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <iomanip>
#include <stack>

using namespace std;
 

int In(char e)
{
	if(e=='(' || e==')' || e=='+' || e=='-' || e=='*' || e=='/') return 1;
	else return 0;
}
int cmp(char c)
{
	switch(c)
	{
		case '+':
		case '-': return 1;
		case '*':
		case '/': return 2;
		default : return 0;	
	}	
}
double calculate(char op,double k1,double k2)
{
	double k;
	switch (op)
	{
		case '+': k = k1+k2; break;
		case '-': k = k1-k2; break;
		case '*': k = k1*k2; break;
		case '/': k = k1/k2; break;
	}
	return k;
}

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

*/

void change(char str[])
{
	int t,i,k,m;
	char e,buf[1002],op,s[1002];
	double kk,k1,k2;
	stack <char> S1;
	stack <double> S2;
	k=0;
	S1.push('=');
	for(i=0;i<strlen(str)-1;++i) //最后一位是 = 
	{
			if( In(str[i])  )
			{				
				switch(str[i])
				{
					case '(': S1.push(str[i]); break;
					case ')': //遇到右括号, 
						while(S1.top()!='(')//弹出栈元素输出 直到 (,
						{
							s[k++]=S1.top();
							k1 = S2.top(); S2.pop();
							k2 = S2.top(); S2.pop();
							S2.push(calculate(S1.top(),k2,k1));
							S1.pop();	
						}
						if(S1.top()=='(')//弹出(不输出
						{
							S1.pop();	
						} 

						break;
					default :
						while(cmp(str[i])<=cmp(S1.top()))
						{
							s[k++]=S1.top();
							k1 = S2.top(); S2.pop();
							k2 = S2.top(); S2.pop();
							S2.push(calculate(S1.top(),k2,k1));
							S1.pop();	
						}
						S1.push(str[i]);
						break;
				}//switch
			}//if
			else{

				sscanf(str+i,"%[^=()+*/-]",buf); //操作数 
				for(m=0;m<strlen(buf);m++) s[k++]=buf[m];
				//printf("%s",buf);
				i += strlen(buf)-1;
				kk = atof(buf);
				//printf("k = %lf\n",k);
				S2.push(kk);

			}

			
		}//for
		while(!S1.empty())
		{
			if(S1.top()!='(' && S1.top()!='=')
			{
				s[k++]=S1.top();
				k1 = S2.top(); S2.pop();
				k2 = S2.top(); S2.pop();
				S2.push(calculate(S1.top(),k2,k1));
			}
				
			S1.pop();
		}

		for(i=0;i<k;i++) printf("%c",s[i]);
		printf("=\n");
		printf("%.2lf\n",S2.top());		
} 
int main()
{
	int t,i;
	char e,str[1002],buf[1002],op;
	double k,k1,k2;
		
	scanf("%d",&t); getchar();
	while(t--)
	{
		
		gets(str); 
		//puts(str);
		change(str);
		
		if(t>0) printf("\n");
	}

	return 0;
}
/*
20
1+2=
(19+21)*3-4/5=

*/
        


注意:中缀表达式转为后缀表达式的方法。。。。。。