中缀表达式转后缀表达式

对于考研而言，这种东西一般应该只会设计到+-*/()和正整数。
那么写起来就很好办了。

抄一下课本上的两个结论：

1.在扫描exp遇到一个运算符op时，如果栈为空，直接将其进栈， 如果栈不为空，只有当op的优先级高于栈顶运算符的优先级的时候才把op进栈， 否则依次出栈运算符并存入postexp，直到栈顶的运算符的优先级小于op的优先级为止， 然后再将op进栈。

2.在扫描exp时遇到（，那么直接入栈，如果遇到），那么不断出栈直至把一个（出栈。

代码：

#include<bits/stdc++.h>
using namespace std;

stack<char> sta;

bool isDigital(char c)
{
	if(c>='0'&&c<='9')return 1;
	return 0;
}

int main()
{
	freopen("in.txt","r",stdin);
	while(cin.peek()!='\n'&&cin.peek()!=EOF)
	{
		char c=cin.peek();
		//处理数字 
		if(isDigital(c))
		{
			string str="";
			while(isDigital(c)||c=='.')
			{
				str+=c;
				cin.get();
				c=cin.peek();
			}
			cout<<str;
		}
		else
		{
			//处理+-*/()
			if(c=='(') cin.get(),sta.push(c);
			if(c==')') 
			{
				cin.get();
				while(sta.top()!='(')
				{
					cout<<sta.top();
					sta.pop();
				}
				sta.pop();
			}
			if(c=='+'||c=='-')
			{
				cin.get();
				while(sta.size()!=0&&sta.top()!='(')
				{
					cout<<sta.top();
					sta.pop();
				}
				sta.push(c);
			}
			if(c=='*'||c=='/')
			{
				cin.get();
				while(sta.top()=='*'||sta.top()=='/')
				{
					cout<<sta.top();
					sta.pop();
				}
				sta.push(c);
			}
		}
	}
	while(sta.size())
	{		
		cout<<sta.top();
		sta.pop();
	}
	return 0;
}

但是在acm里，就又多了正负数，小数。

#include<iostream>
#include<stack>
#include<cstring>
#include<iomanip>
using namespace std;

stack<char> sta;
string str;
char c;
char last='1';
void solve()
{
	while(cin.peek()!='\n')
	{
		c=cin.get();
		//cout<<"what"<<endl;
		//cout<<c<<endl;
		if(c>='0'&&c<='9')
		{
			str+=c;
			while((cin.peek()>='0'&&cin.peek()<='9')||cin.peek()=='.')
			{
				c=cin.get();
				str+=c;
			}
			str+=' ';
		}
		if(c=='+'||c=='-')
		{
			if(str.size()==0||(last=='+'||last=='-'||last=='*'||last=='/'||last=='('))
			{
				if(c!='+')
				str+=c;
			}
			else
			{
				if(!sta.empty()&&(sta.top()=='*'||sta.top()=='/'))
				{
					while(!sta.empty()&&sta.top()!='(')
					{
						str+=sta.top();
						str+=' ';
						sta.pop();
					}
				}
				sta.push(c);
			}	
		}
		if(c=='*'||c=='/')
		{
			sta.push(c);
		}
		if(c=='(')sta.push(c);
		if(c==')')
		{
			while(sta.top()!='(')
			{
				str+=sta.top();
				str+=' ';
				sta.pop();
			}
			sta.pop();
		}
		last=c;
	}
	while(!sta.empty())
	{
		str+=sta.top();
		str+=' ';
		sta.pop();
	}
}

void output()
{
	for(int i=0;i!=str.size()-1;i++)
	{
		cout<<str[i];
	}
	cout<<endl;
}

int main()
{	
	solve();
	output();
	return 0;
}