前缀表达式求值

这简单，可以递归求解，遇到一个符号，直接往下递归。

这里我的处理是有空格的，因此呢可以使用atof将字符串转化了double，atoi好像是转化为int。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<queue>
#include<map>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
char s[10005];
double dfs(){
	scanf ("%s",s);
	double x = atof(s);
	if (s[0] == '*')
		return dfs() * dfs();
	if (s[0] == '+')
		return dfs() + dfs();
	if (s[0] == '-')
		return dfs() - dfs();
	if (s[0] == '/')
		return dfs() / dfs();
	return x;
}
int main(){
	printf("%lf",dfs());
}

中缀表达式求值

考试考过，当时没模拟出来，QWQ。

事后发现其实也挺简单的。

中缀表达式就一个点，那就是符号的优先级。括号其实都好处理，我们用栈，当右括号出现时就直接去弹栈，弹出左括号为止。

那么怎么处理符号的优先级呢。

我们直接看四则运算吧，因为如果有乘方的话，思路其实是一样的。中缀式，我们将左括号看做优先级最低，右括号则最高。

我们用两个栈，一个放符号，一个放数字，用一个栈总感觉很乱，不好处理。

1.数字直接放入栈中。

2.当运算符号放入栈时，进行判断，要开始弹栈了。弹栈操作很简单，即取一个符号，两个数，进行运算再将结果放回去。注意减法除法顺序。关键是条件判断。（简单来说总体就是维护栈中符号优先级单调下降）

(1).栈顶元素优先级大于等于当前要加入的元素，那么弹出栈顶元素并进行计算。

(2).遇到了左括号或栈为空，则停止弹栈，加入元素。

3.遇到右括号，一直弹到左括号。

这里不给代码，给一个恶心的题目链接（T3）

后缀表达式求值

也挺简单的，用栈，遇到符号取两个数进行运算，遇到数字装进去。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<stack>
#include<queue>
#include<vector>
#include<cstdlib>
#include<algorithm>
using namespace std;
char s[1005];
stack<int>a;
void dfs()
{
	while (scanf ("%s",s)!=EOF)
	{
		int x=atoi(s);
		if (x!=0)
		{
			a.push(x);
			continue;
		}
		x=a.top();
		a.pop();
		int y=a.top();
		a.pop();
		if (s[0]=='+')
			a.push(x+y);
		if (s[0]=='-')
			a.push(y-x);
		if (s[0]=='*')
			a.push(x*y);
		if (s[0]=='/')
			a.push(y/x);
	}
	printf("%d",a.top());
}
int main()
{
	//freopen("postfix.in","r",stdin);
	//freopen("postfix.out","w",stdout);
	dfs();
}