前缀表达式和后缀表达式 - C++代码

速览

算术表达式分为：

前缀表达式(波兰式)
后缀表达式(逆波兰式)
中缀表达式

中缀表达式是我们最熟悉的表达式，是常见的运算式，如下所示：

(2 + 3) * 4 - 5
1

这就是一个中缀表达式
相对于中缀表达式，前缀表达式的运算符在操作数之前，把上面的中缀表达式改写成前缀表达式为：

- * + 2 3 4 5
1

注意，并不是所有运算符在所有数字之前，如：

+ - 1 2 * 3 5
1

也可以是前缀表达式

前缀表达式

前缀表达式的运算规则

从右向左依次扫描表达式，如果扫描到数字，则把数字压入栈
如果扫描到运算符，则依次弹出栈顶的两个数字进行计算，并把计算结果压入栈

例：计算前缀表达式 - * +2345 的值

扫描值	堆栈	计算值
5	5
4	5 4
3	5 4 3
2	5 4 3 2
+	5 4 5	2+3=5
*	5 20	5*4=20
-	15	20-5=15

前缀表达式的值为 15

中缀表达式转换为前缀表达式

创建2个空栈 S1 和 S2，S1 为符号栈，S2 为临时栈，从右向左扫描中缀表达式

如果遇到数字，压入 S2 栈中
如果遇到符号：
如果 S1 为空栈，或者 S1 栈顶为右括号，直接压入 S1 中
如果扫描到的符号优先级大于等于 S1 栈顶的符号，直接压入 S1 中
如果扫描到的符号优先级小于 S1 栈顶的符号，则把 S1 栈顶的符号弹出并压入 S2，重复这一步骤，直到可以把扫描到的符号压入 S1
如果遇到括号：
如果遇到左括号，直接压入 S1
如果遇到右括号，依次弹出 S1 栈顶的符号并压入 S2，直到遇到左括号时，丢弃这一对括号
最后，依次把 S1 栈顶元素弹出压入 S2 中，依次弹出 S2 栈顶元素，得到前缀表达式

例：把中缀表达式 1+((2+3) * 4)-5 转换为前缀表达式

扫描值	操作	S1	S2
5	压入S2		5
-	压入S1	-	5
)	压入S1	-)	5
4	压入S2	-)	5 4
*	压入S1	-)*	5 4
)	压入S1	-)*)	5 4
3	压入S2	-)*)	5 4 3
+	压入S1	-)*)+	5 4 3
2	压入S2	-)*)+	5 4 3 2
(	弹出+，压入S2	-)*	5 4 3 2+
(	弹出*，压入S2	-	5 4 3 2+*
+	压入S1	-+	5 4 3 2+*
1	压入S2	-+	5 4 3 2+*1
NULL	依次弹出S1栈顶压入S2		5 4 3 2+*1+ -

所求前缀表达式为：-+1*+2345

代码实现：

// 前缀表达式练习 - 只能输入 0-9 的数
#include<iostream>
using std::cin;
using std::cout;
using std::endl;
#include<string>
using std::string;
#include<stack>
using std::stack;

bool isoperator(int _C);
bool isbrackets(int _C);

int main(int argc, char*argv[]) {
	// 输入中缀表达式
	string infix;
	cin >> infix;
	// 中缀表达式 => 前缀表达式
	stack<char>S1, S2;
	for (auto it = infix.crbegin(); it != infix.crend(); it++) {
		if (isdigit(*it))S2.push(*it);
		else if (isoperator(*it)) {
		CASE_ISOPERATOR:
			if (S1.empty() || ')' == S1.top())S1.push(*it);
			else if ('+' == S1.top() || '-' == S1.top())S1.push(*it);
			else if ('*' == *it || '/' == *it)S1.push(*it);
			else {
				S2.push(S1.top());
				S1.pop();
				goto CASE_ISOPERATOR;
			}
		}
		else if (isbrackets(*it)) {
			if (')' == *it)S1.push(*it);
			else {
				while (!isbrackets(S1.top())) {
					S2.push(S1.top());
					S1.pop();
				}
				S1.pop();
			}
		}
	}
	while (!S1.empty()) {
		S2.push(S1.top());
		S1.pop();
	}
	string prefix;
	while (!S2.empty()) {
		prefix.push_back(S2.top());
		S2.pop();
	}
	// 计算前缀表达式的值
	stack<int>value;
	for (auto it = prefix.crbegin(); it != prefix.crend(); it++) {
		if (isdigit(*it))value.push(*it - '0');
		else {
			int top, second_top;
			top = value.top();
			value.pop();
			second_top = value.top();
			value.pop();
			switch (*it) {
			case'+':value.push(top + second_top); break;
			case'-':value.push(top - second_top); break;
			case'*':value.push(top*second_top); break;
			case'/':value.push(top / second_top); break;
			}
		}
	}
	// 输出前缀表达式及其值
	cout << prefix << '=' << value.top() << endl;
	return 0;
}

bool isoperator(int _C) {
	return '+' == _C || '-' == _C || '*' == _C || '/' == _C ? true : false;
}

bool isbrackets(int _C) {
	return '(' == _C || ')' == _C ? true : false;
}
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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

后缀表达式

后缀表达式的运算

从左向右依次扫描表达式，如果扫描到数字，则把数字压入栈
如果扫描到运算符，则弹出栈顶的两个数字进行计算，并把计算结果压入栈
（和前缀表达式不同，结果 = 次顶数字 operator 顶部数字）

例：计算后缀表达式 23+4 * 5- 的值

扫描值	堆栈	计算值
2	2
3	2 3
+	5	2+3=5
4	5 4
*	20	5*4=20
5	20	5
-	15	20-5=15

后缀表达式的值为 15

中缀表达式转换为后缀表达式

创建2个空栈 S1 和 S2，S1 为符号栈，S2 为临时栈，从左向右扫描中缀表达式

如果遇到数字，压入 S2 栈中
如果遇到符号：
如果 S1 为空栈，或者 S1 栈顶为左括号，直接压入 S1 中
如果扫描到的符号优先级大于 S1 栈顶的符号，直接压入 S1 中
(注意前缀表达式是大于等于，而后缀表达式只有大于才可以直接压入)
如果扫描到的符号优先级小于 S1 栈顶的符号，则把 S1 栈顶的符号弹出并压入 S2，重复这一步骤，直到可以把扫描到的符号压入 S1
如果遇到括号：
如果遇到右括号，直接压入 S1
如果遇到左括号，依次弹出S1栈顶的符号并压入 S2，直到遇到左括号时，丢弃这一对括号
最后，依次把 S1 栈顶元素弹出压入 S2 中，依次弹出 S2 栈顶元素，“反向输出”，得到前缀表达式