[数据结构与算法]信息学奥赛一本通 1331：【例1-2】后缀表达式的值

【题目链接】

ybt 1331：【例1-2】后缀表达式的值

【题目考点】

1. 表达式求值

2. 表达式树

表达式树：一棵表达式树可以表示一系列的运算。
表达式树中的结点包括运算符与数值

struct Node
{
	char c;//运算符
	int n;//数值
}

• 分支结点：c:运算符，n:该子树对应的表达式的值
• 叶子结点：c:'\0'，n:数值
  表达式树的值，是左子树的值和右子树的值，经过根结点运算符运算后得到的结果。

【解题思路】

题目中说参与运算的整数及结果的绝对值均在$2^{64}$范围内，意思指的就是数据类型要设为long long。
（虽说$2^{6}3$及更大的数字不能用long long正确表示，但题目中实际上没有这么大的数字，用long long即可。）

解法1：后缀表达式直接求值

1. 从左向右扫描后缀表达式。
2. 遇到数字时，将数字入栈。
3. 遇到运算符时，弹出栈顶的两个数，用该运算符对它们做相应的计算，结果入栈。
4. 扫描结束后，栈顶数字就是结果。

解法2：后缀表达式构造表达式树

1. 如果读到数字，那么新建数字结点入栈。
2. 如果读到运算符，则新建运算符结点np，出栈两个结点，将这两个结点的值通过np的运算符运算后得到的值存为新结点np的值，将np入栈。
3. 读完整个后缀表达式，栈中应该只剩1个结点，该结点就是表达式树的根结点，该结点的值就是表达式的值 。

解法3：递归

先将字符串处理为由结构体对象构成的后缀表达式，每个结构体对象可能是数字可能是运算符。
后缀表达式的结构为：<第一个运算单元><第二个运算单元><运算符>
每个运算单元也许是一个数字，也许是一个后缀表达式。
后缀表达式数组最后一个元素的下标为p。
设函数solve()，求从第p位置开始向左遍历取到的第一个运算单元的值。每取一个元素，p向左移动一个位置。

• 如果p位置是数字，直接返回这个数字的值。
• 如果p位置是运算符，那么从p位置开始向左取两个运算单元的值，并用当前位置的运算符进行计算，得到这一运算单元的值。

【题解代码】

解法1：后缀表达式直接求值

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;//用LL代替long long 
stack<LL> stk;
LL calc(LL a, LL b, char c)//数字a，b和运算符c，运算后的值 
{
	switch(c)
	{
		case '+':
			return a+b;
		case '-':
			return a-b;
		case '*':
			return a*b;
		case '/':
			return a/b;
	}
}
int main()
{
	char s[260];//读入整个字符串 
	LL num = 0;//保存分解出来的数字 
	cin.getline(s, 260);
	for(int i = 0; s[i] != '@'; ++i)//遍历字符串 
	{
		if(s[i] >= '0' && s[i] <= '9')//如果是数字字符，则构造数字num 
			num = num * 10 + (s[i] - '0');
		else if(s[i] == ' ')//如果遇到空格，完成数字num的构造，将num压栈 
		{
			stk.push(num);
			num = 0;
		}
		else//如遇到运算符，出栈两个数，进行计算 
		{
			LL b = stk.top();//第二个运算数 
			stk.pop();
			LL a = stk.top();//第一个运算数 
			stk.pop();
            stk.push(calc(a, b, s[i]));
		}
	}
	cout << stk.top();//最后栈中剩下的数字，就是最后的结果。出栈并输出它。	
	return 0;
}

解法2：后缀表达式构造表达式树

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;//用LL代替long long 
struct Node
{
    char c;//运算符 
    LL n;//数字
    int left, right;
};
Node node[300];
int p;//node数组的下标 
stack<int> stk;
LL calc(LL a, LL b, char c)//数字a，b和运算符c，运算后的值 
{
	switch(c)
	{
		case '+':
			return a+b;
		case '-':
			return a-b;
		case '*':
			return a*b;
		case '/':
			return a/b;
	}
}
int main()
{
	char s[260];//读入整个字符串 
	LL num = 0;//保存分解出来的数字 
	cin.getline(s, 260);
	for(int i = 0; s[i] != '@'; ++i)//遍历字符串 
	{
		if(s[i] >= '0' && s[i] <= '9')//如果是数字字符，则构造数字num 
			num = num * 10 + (s[i] - '0');
		else if(s[i] == ' ')//如果遇到空格，完成数字num的构造，将数字结点压栈 
		{
		    node[++p].n = num;
			stk.push(p);
			num = 0;
		}
		else//如遇到运算符，新建运算符结点，出栈两个结点，作为运算符结点的子树 
		{
		    int pb = stk.top();//第二个运算数结点地址 
		    stk.pop();
		    int pa = stk.top();//第一个运算数结点地址 
			stk.pop();
			node[++p].c = s[i];
			node[p].n = calc(node[pa].n, node[pb].n, node[p].c);
			node[p].left = pa, node[p].right = pb;//设左右子树 
            stk.push(p);//将新的运算符结点的地址入栈 
		}
	}
	int root = stk.top();//最后栈中剩下的是表达式树根结点的地址
	cout << node[root].n;//根结点的值就是整个表达式树的值 
	return 0;
}

解法3：递归

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;//用LL代替long long 
struct Node
{
    char c;//运算符 
    LL n;//数字
};
Node eq[300];//转化后的后缀表达式 
int p;//node数组的下标 
stack<int> stk;
LL calc(LL a, LL b, char c)//数字a，b和运算符c，运算后的值 
{
	switch(c)
	{
		case '+':
			return a+b;
		case '-':
			return a-b;
		case '*':
			return a*b;
		case '/':
			return a/b;
	}
}
LL solve()//如果node[p]是数字，返回该数字。如果node[p]是运算符，返回以第p位置为运算符的后缀表达式的值  
{
    int e = p--;
    if(eq[e].c == '\0')//如果是数字 
        return eq[e].n;
    else//如果是运算符 
    {
        LL b = solve();
        LL a = solve();
        return calc(a, b, eq[e].c);
    }   
} 
int main()
{
	char s[260];//读入整个字符串 
	LL num = 0;//num:保存分解出来的数字
	cin.getline(s, 260);
	for(int i = 0; s[i] != '@'; ++i)//遍历字符串 
	{
		if(s[i] >= '0' && s[i] <= '9')//如果是数字字符，则构造数字num 
			num = num * 10 + (s[i] - '0');
	    else if(s[i] == ' ')//如果遇到空格，完成数字num的构造
	    {
            eq[++p].n = num;
	        num = 0;   
        }
        else//如遇到运算符 
			eq[++p].c = s[i];
	}
	//此时p指向最后一个位置 
	cout << solve();
	return 0;
}