栈在表达式中的应用

算术表达式

算术表达式由操作数、运算符和界限符组成。其中界限符反应计算顺序，因此必不可少。

那么有没有可能不用界限符也能正确的表达运算顺序呢？欸，有的。

波兰表示法（Polish notation，或波兰记法），是一种逻辑、算术和代数表示方法，其特点是操作符置于操作数的前面，因此也称做前缀表示法。如果操作符的元数（arity）是固定的，则语法上不需要括号仍然能被无歧义地解析。

逆波兰表示法（Reverse Polish notation，RPN，或逆波兰记法），是一种是由波兰数学家扬·武卡谢维奇1920年引入的数学表达式形式，在逆波兰记法中，所有操作符置于操作数的后面，因此也被称为后缀表示法。逆波兰记法不需要括号来标识操作符的优先级。

类型	形式	例
中缀表达式	操作数 运算符 操作数	A + B
后缀表达式	操作数 操作数 运算符	AB +
前缀表达式	运算符 操作数 操作数	+ AB

后缀表达式求值

手算方法

从左往右依次扫描后缀表达式的每一个字符，若该字符是运算符，则选择运算符左侧最近的两个操作数进行相应运算，注意左右顺序，将得到的计算结果替换掉这三个字符。例如2 3 4 + 5 * 5 +，第一次运算后为2 7 5 * 5 +。如此反复直到扫面完全部字符。

代码实现

从左往右依次扫描后缀表达式的每一个字符

1. 若该字符是操作数，则入栈
2. 若该字符是运算符，则从栈顶出栈两个字符（先出栈的是右操作数），进行该运算符的运算，并将计算结果入栈。
3. 扫描结束，最后栈顶为这个后缀表达式的计算结果。

前缀表达式求值

手算方法

从右往左依次扫描前缀表达式的每一个字符，若该字符是运算符，则选择运算符右侧最近的两个操作数进行相应运算，注意左右顺序，将得到的计算结果替换掉这三个字符。例如+ 2 * + 3 4 5，第一次运算后为+ 2 * 7 5。如此反复直到扫面完全部字符。

代码实现

从右往左依次扫描后缀表达式的每一个字符

1. 若该字符是操作数，则入栈
2. 若该字符是运算符，则从栈顶出栈两个字符（先出栈的是左操作数），进行该运算符的运算，并将计算结果入栈。
3. 扫描结束，最后栈顶为这个前缀表达式的计算结果。

中缀表达式转后缀表达式

手算方法

1. 按照运算符的运算顺序对所有运算单位加括号。（左优先）
2. 将运算符移至对应括号的后面，相当于按“左操作数 右操作数 运算符”重新组合。
3. 去除所有括号。

转化前的中缀表达式	加括号	转换后的后缀表达式
A+B*(C-D)-E/F	((A+(B*(C-D)))-(E/F))	ABCD-*+EF/-
A+(B+C)*D	(A+((B+C)*D))	ABC+D*+
A+B*C/D	(A+( (B*C) /D))	ABC*D/+

注意第三个例子，按照左优先，因此应先括B*C.

代码实现

中缀表达式转后缀表达式应该从左到右依次扫描。

具体过程如下：

1. 当前字符是操作数，直接加入后缀表达式。
2. 当前字符是界限符。
   1. 若为(，则直接入栈
   2. 若为)且栈非空，则依次弹出栈中的运算符，并加入后缀表达式，直到弹出(位置。
3. 当前字符是运算符
   1. 若其优先级>除了(外的栈顶运算符，则直接入栈。
   2. 若其优先级<=栈顶运算符，则弹出栈顶运算符，并加入后缀表达式，之后重复判断。
4. 将栈中剩余元素加入后缀表达式。

//后缀表达式
vector<char> ans;
string s;
cin >> s;
//待处理序列
for (int i = 0;i < s.size();i ++) {
	char ch = s[i];
	cout << "当前字符：" << ch << endl;
	if (ch != '(' and ch != ')') {	//不为界限符
		// 是否为运算符
		if (ch == '+' or ch == '-' or ch == '*' or ch == '/') {
			// 优先级高于其他两种
			if (ch == '*' or ch == '/') {

				// 栈中优先级高于或等于当前运算符
                 //则弹出加入后缀表达式
				while ((st[idx] == '*' or st[idx] == '/') and idx != -1 and st[idx] != '(') {
			
					ans.push_back(st[idx --]);
				}
				st[++ idx] = ch;
				
			} else {
				// 栈中优先级高于或等于当前运算符，则弹出加入后缀表达式
				while(st[idx] != '(' and idx != -1) {
					ans.push_back(st[idx --]);
				}
				st[++ idx] = ch;
			}
		} else {	// 操作数直接加入后缀表达式
			ans.push_back(ch);
		}
	} else {
		if (ch == '(') {
			st[++ idx] = ch;
		} else {
			while(st[idx] != '(') {
				ans.push_back(st[idx --]);
			}
			if (st[idx] == '(') {
				st[idx --];
			}
		}
	}
	//show
	for (int i = 0;i < ans.size();i ++) 
		cout << ans[i];
	cout << endl <<  "-----" << endl;
	cout << "栈内：";
	for (int i = 0;i <= idx;i ++)
		cout << st[i];
	cout << endl <<  "*****" << endl;
	cout <<endl;
}
//弹出剩余运算符
while(idx != -1) {
	ans.push_back(st[idx --]);
}
for (int i = 0;i < ans.size();i ++) {
	cout << ans[i];
}

中缀表达式转前缀表达式

手算方法

1. 按照运算符的运算顺序对所有运算单位加括号。（右优先）
2. 将运算符移至对应括号的前面，相当于按“ 运算符 左操作数 右操作数”重新组合。
3. 去除所有括号。

转化前的中缀表达式	加括号	转换后的前缀表达式
A+B*(C-D)-E/F	(A+((B*(C-D))-(E/F)))	+A-*B-CD/EF
A+(B+C)*D	(A+((B+C)*D))	+A*+BCD
A+B*C/D	(A+(B* (C/D) ))	+A*B/CD

注意第三个例子，按照右优先，因此应先括C/D.

代码实现

中缀表达式转前缀表达式应该从右到左依次扫描。

具体过程如下：

1. 当前字符是操作数，直接加入前缀表达式。
2. 当前字符是界限符。
   1. 若为)，则直接入栈
   2. 若为(且栈非空，则依次弹出栈中的运算符，并加入后缀表达式，直到弹出)位置。
3. 当前字符是运算符
   1. 若其优先级<除了)外的栈顶运算符，则直接入栈。
   2. 若其优先级>=栈顶运算符，则弹出栈顶运算符，并加入前缀表达式，之后重复判断。
4. 将栈中剩余元素加入前缀表达式。

注意：最后的结果应该是逆序输出。

//前缀表达式
vector<char> ans;
//待处理序列
string s;
cin >> s;
// 从右到左遍历
for (int i = s.size() - 1;i >= 0;i --) {
	char ch = s[i];
	// cout << "当前字符：" << ch << endl;
	if (ch != '(' and ch != ')') {	//不为界限符
		// 是否为运算符
		if (ch == '+' or ch == '-' or ch == '*' or ch == '/') {
			// 优先级高于其他两种
			// 栈顶元素优先级 > 当前运算符优先级，则出栈加入前缀表达式
			// 直到当前运算符优先级 >= 栈顶运算符优先级，入栈
			if (ch == '-' or ch == '+') {
				while((st[idx] == '*' or st[idx] == '/') and idx != -1) {
					ans.push_back(st[idx --]);
				}
			} 
			st[++ idx] = ch;
		} else {	// 操作数直接加入前缀表达式
			ans.push_back(ch);
		}
	} else {
		if (ch == ')') {
			st[++ idx] = ch;
		} else {
			while(st[idx] != ')') {
				ans.push_back(st[idx --]);
			}
			if (st[idx] == ')') {
				st[idx --];
			}
		}
	}
	//show
		for (int i = 0;i < ans.size();i ++) 
		cout << ans[i];
	cout << endl <<  "-----" << endl;
	cout << "栈内：";
	for (int i = 0;i <= idx;i ++)
		cout << st[i];
	cout << endl <<  "*****" << endl;
	cout <<endl;
}
//弹出剩余运算符
while(idx != -1) {
	ans.push_back(st[idx --]);
}
// 逆序输出
for (int i = ans.size() - 1;i >= 0;i --) {
	cout << ans[i];
}