首页 > 代码库 > NYOJ 35 表达式求值

NYOJ 35 表达式求值

一个模板了 哈哈.

这题因为已经包含了整形、浮点形了,以后也不需要特别处理了。

/*
这里主要是逆波兰式的实现,使用两个stack 这里用字符串来模拟一个stack,第一步,将中缀表达式转变为后缀表达式
第二步,然后再使用一个stack,计算后缀表达式的结果,这一步很容易出错,考虑到浮点数的问题。
*/
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <stack>
#include <iomanip>
using namespace std;
int cmp(char ch)     // 运算符优先级
{
	switch(ch)
	{
		case '+':
		case '-': return 1;
		case '*':
		case '/': return 2;
		default : return 0;
	}
}
void change(char *s1,char *s2)       // 中缀表达式转变后缀表达式
{
	stack <char> s;
	s.push('#');
	int i = 0,len=strlen(s1),cnt=0;
	while(i < len-1) //现在输入的是1.000 +2 /4=,如果是1.000+2/4的话需要把-1去掉
	{
	    if(s1[i]==' ')
        {
            i++;
            continue;
        }
		else if(s1[i] == '(')
		{
			s.push(s1[i++]);
		}
		else if(s1[i] == ')')
		{
			while(s.top() != '(')
			{
			    s2[cnt++]=s.top();
				s2[cnt++]= ' ';
				s.pop();
			}
			s.pop();
			i++;
		}
		else if(s1[i] == '+'||s1[i] == '-'||s1[i] == '*'||s1[i] == '/')
		{
			while(cmp(s.top()) >= cmp(s1[i]))
			{
				s2[cnt++]=s.top();
				s2[cnt++]= ' ';
				s.pop();
			}
			s.push(s1[i]);
			i++;
		}
		else
		{
			while('0' <= s1[i]&&s1[i] <= '9'||s1[i] == '.')
			{
			    s2[cnt++]=s1[i++];
			}
            s2[cnt++]= ' ';
		}
	}
	while(s.top() != '#')
	{
		s2[cnt++]=s.top();
        s2[cnt++]= ' ';
		s.pop();
	}
	s2[cnt]='\0';
}
double value(char *s2)         // 计算后缀表达式,得到其结果。
{
	stack < double> s;
	double x,y;
	int i = 0,len=strlen(s2);
	while(i < len)
	{
		if(s2[i] == ' ')
		{
			i++;
			continue;
		}
		switch(s2[i])
		{
			case '+': x = s.top(); s.pop(); x += s.top(); s.pop(); i++; break;
			case '-': x = s.top(); s.pop(); x =s.top()-x; s.pop(); i++; break;
			case '*': x = s.top(); s.pop(); x *= s.top(); s.pop(); i++; break;
			case '/': x = s.top(); s.pop(); x = s.top()/x; s.pop(); i++; break;
			default :
			{
				x = 0;
				while('0' <= s2[i]&&s2[i] <= '9')
				{
					x = x*10+s2[i] - '0';
					i++;
				}
				if(s2[i] == '.')
				{
					double k = 10.0;
					y = 0;
					i++;
					while('0' <= s2[i]&&s2[i] <= '9')
					{
						y += ((s2[i]-'0')/k);
						i++;
						k *= 10;
					}
					x += y;
				}
			}
		}
		s.push(x);
	}
	return s.top();
}
char s1[1006],s2[1006];
int main()
{
	int n;
	scanf("%d",&n);
	getchar();
	while(n--)
	{
		gets(s1);
		change(s1,s2);
		printf("%.2f\n",value(s2));
	}
	return 0;
}
/*
2
1.000 +2 / 4=
((1+2 )* 5+1) /4=
*/


NYOJ 35 表达式求值