洛谷 P1449 后缀表达式

【题目链接】

洛谷 P1449 后缀表达式

【题目考点】

1. 表达式求值

2. 表达式树

【解题思路】

具体思路见
信息学奥赛一本通 1331：【例1-2】后缀表达式的值
本题与上题基本相同。区别有：

• 上题中用数字后面是空格，本题中数字后面是’.'。
• 上题数字范围达到了long long，本题数字范围为int。
• 上题输入字符串最长为250，本题输入字符串最长为50。

因此把上题题解代码中的' '变为'.'，long long变为int，再修改一下数组长度，即为本题的题解代码。

【题解代码】

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

#include 
using namespace std;
#define N 55 
int calc(int a, int 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()
{
	stack<int> stk;
	char s[N];//读入整个字符串 
	int num = 0;//保存分解出来的数字 
	cin.getline(s, N);
	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//如遇到运算符，出栈两个数，进行计算 
		{
			int b = stk.top();//第二个运算数 
			stk.pop();
			int a = stk.top();//第一个运算数 
			stk.pop();
            stk.push(calc(a, b, s[i]));
		}
	}
	cout << stk.top();//最后栈中剩下的数字，就是最后的结果。出栈并输出它。	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

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

#include 
using namespace std;
#define N 55
struct Node
{
    char c;//运算符 
    int n;//数字
    int left, right;
};
Node node[N];
int p;//node数组的下标 
stack<int> stk;
int calc(int a, int 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[N];//读入整个字符串 
	int num = 0, np;//保存分解出来的数字 
	cin.getline(s, N);
	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的构造，将数字结点压栈 
		{
			np = ++p;
		    node[np].n = num;
			stk.push(np);
			num = 0;
		}
		else//如遇到运算符，新建运算符结点，出栈两个结点，作为运算符结点的子树 
		{
		    int pb = stk.top();//第二个运算数结点地址 
		    stk.pop();
		    int pa = stk.top();//第一个运算数结点地址 
			stk.pop();
			np = ++p;
			node[np].c = s[i];
			node[np].n = calc(node[pa].n, node[pb].n, node[np].c);
			node[np].left = pa, node[np].right = pb;//设左右子树 
            stk.push(np);//将新的运算符结点的地址入栈 
		}
	}
	int root = stk.top();//最后栈中剩下的是表达式树根结点的地址
	cout << node[root].n;//根结点的值就是整个表达式树的值 
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

解法3：递归

#include
using namespace std;
#define N 55
struct Node
{
    int n;
    char c;
};
Node eq[N];//保存后缀表达式 
int p;
int calc(int a, int b, char c) 
{
	switch(c)
	{
		case '+':
			return a+b;
		case '-':
			return a-b;
		case '*':
			return a*b;
		case '/':
			return a/b;
	}	
}
int solve()//递归求解后缀表达式 
{
    int i = p--;
    if(eq[i].c)//如果公式第i元素是运算符 
    {
        int b = solve();//递归求出第二个运算单元的值 
        int a = solve();//递归求出第一个运算单元的值 
        return calc(a, b, eq[i].c);
    }
    else
        return eq[i].n;
}
int main()
{
    string s;
    cin >> s;
    int num = 0;
    for(int i = 0; s[i] != '@'; ++i)
    {
        if(s[i] >= '0' && s[i] <= '9')
            num = num*10 + s[i]-'0';
        else if(s[i] == '.')
        {
            eq[++p].n = num;
            num = 0;
        }
        else
            eq[++p].c = s[i];
    }
	cout << solve();//求后缀表达式eq的值 
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56