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

逆波兰表达式定义

逻辑提问式类似于算术表达式，对于检索而言，这种表达式并不是最优和最简洁的形式，需要进行必要的转换。1929年波兰的逻辑学家卢卡西维兹(Jan Lucasiewicz)提出了将运算符放在运算项后面的逻辑表达式，又称“逆波兰表达式”。采用这种表达式组织逻辑提问式非常方便检索运算，是日本的福岛先生最早将逆波兰表达式应用于情报检索的，故又称为“福岛方法”。
逆波兰表达式又叫做后缀表达式，是一种没有括号，并严格遵循“从左到右”运算的后缀式表达方法，如下表所示：

算法步骤

1、首先构造一个运算符栈，此运算符在栈内遵循越往栈顶优先级越高的原则。
2、读入一个用中缀表示的简单算术表达式，为方便起见，设该简单算术表达式的右端多加上了优先级最低的特殊符号“#”。
3、从左至右扫描该算术表达式，从第一个字符开始判断，如果该字符是数字，则分析到该数字串的结束并将该数字串直接输出。
4、如果不是数字，该字符则是运算符，此时需比较优先关系。
具体做法是：将该字符与运算符栈顶的运算符的优先关系相比较。如果该字符优先关系高于此运算符栈顶的运算符，则将该运算符入栈。若不是的话，则将栈顶的运算符从栈中弹出，直到栈项运算符的优先级低于当前运算符，将该字符入栈。
5、重复步骤1～2，直至扫描完整个简单算术表达式，确定所有字符都得到正确处理，便可以将中缀式表示的简单算术表达式转化为逆波兰表示的简单算术表达式。

以上内容取自百度百科。

因为逆波兰表达式更加常用，而百科上对于波兰表达式的描述很简略，在此就先省略波兰表达式的介绍。只要知道波兰表达式和逆波兰表达式很相似就可以了，前者是前缀表达式，即运算符在即将进行运算的数字之前，后者是后缀表达式，同理。

预备知识如下：

了解函数：atof()函数的头文件是<cstdlib>，其作用是将字符串转化为double类型。函数原型：double atof(const char *str)
简述思路：将中缀表达式转化为逆波兰(波兰)表达式，遇到左(右)括号直接入栈，遇到右(左)括号则从栈顶到对应的左(右)括号全部出栈，但括号不需要放入表达式中。其它运算符根据运算符优先级，优先级小的运算符入栈前将栈顶优先级大的运算符全部弹出，如果没有更大的直接放入栈中。

生成逆波兰表达式
注意从左往右读取

#include<map>
#include<stack>
#include<cstdio>
using namespace std;
const int inf = 0x3f3f3f3f;
map<char,int>priority;
stack<char>s;
int flag = 0;
int main(void) {
	freopen("in.txt", "r", stdin);
	priority['+'] = priority['-'] = 1;
	priority['*'] = priority['/'] = 2;
	priority['#'] = -1;
	priority[')'] = 0;
	priority['('] = inf;
	s.push('#');
	char a[10];
	while (scanf("%s", a) == 1) {
		if (a[0] == '+' || a[0] == '-' || a[0] == '*' || a[0] == '/' || a[0] == '(' || a[0] == ')') {
			while (!s.empty() && priority[s.top()] >= priority[a[0]] && s.top() != '(') {
				if (flag)printf(" "); else flag = 1;
				printf("%c", s.top()); s.pop(); 
			}
			if (a[0] != ')')s.push(a[0]);
			else s.pop();
		}
		else {
			if (flag)printf(" "); else flag = 1;
			printf("%.lf", atof(a));
		}
	}
	while (s.top() != '#') {
		if (flag)printf(" "); else flag = 1;
		printf("%c", s.top()); s.pop();
	}
	printf("\n");
	return 0;
}

样例：

输入：5 + ( 6 – 4 / 2 ) * 3
输出：5 6 4 2 / - 3 * +

求解逆波兰表达式
注意从左往右读取

#include<stack>
#include<cstdio>
using namespace std;
stack<double>s;
int main(void) {
	char a[10];
	while (scanf("%s", a) == 1) {
		if (a[0] == '+' || a[0] == '-' || a[0] == '*' || a[0] == '/') {
			double t1 = s.top(); s.pop();
			double t2 = s.top(); s.pop();
			switch (a[0]) {
			case'+':t1 = t2 + t1; break;
			case'-':t1 = t2 - t1; break;
			case'*':t1 = t2 * t1; break;
			case'/':t1 = t2 / t1; break;
			}
			s.push(t1);
		}
		else s.push(atof(a));
	}
	printf("%lf\n", s.top());
}

样例：

输入：5 6 4 2 / - 3 * +
输出：17.000000

补充

生成波兰表达式：
注意从右往左读取

#include<stack>
#include<cstdio>
#include<string>
#include<iostream>
using namespace std;
stack<string>in, rep, tmp;
stack<double>s;
int main(void) {
	string t;
	while (cin >> t)in.push(t);
	while (!in.empty()) {
		t = in.top(); in.pop();
		if (t[0] == '+' || t[0] == '-' || t[0] == '*' || t[0] == '/' || t[0] == '(' || t[0] == ')') {
			switch (t[0]) {
			case')':tmp.push(t); break;
			case'(': while (tmp.top() != ")") {
				rep.push(tmp.top()); tmp.pop();
			} tmp.pop();  break;
			case'*':tmp.push(t); break;
			case'/':tmp.push(t); break;
			case'+':while (!tmp.empty() && (tmp.top() == "*" || tmp.top() == "/")) {
				rep.push(tmp.top()); tmp.pop();
			} tmp.push(t); break;
			case'-':while (!tmp.empty() && (tmp.top() == "*" || tmp.top() == "/")) {
				rep.push(tmp.top()); tmp.pop();
			} tmp.push(t); break;
			}
		}
		else rep.push(t);
	}
	while (!tmp.empty()) {
		rep.push(tmp.top());tmp.pop();
	}
	int flag = 0;
	while (!rep.empty()) {
		if (flag)printf(" "); else flag = 1;
		printf("%s", rep.top().c_str());
		rep.pop();
	} printf("\n");
	return 0;
}

样例：

输入：5 + ( 6 - 4 / 2 ) * 3
输出：+ 5 * - 6 / 4 2 3

求解波兰表达式：
注意从左往右读取

#include<cstdio>
#include<cstdlib>
using namespace std;
double exp(){
    char a[10];
    scanf("%s", a);
    switch (a[0]) {
    case '+':return exp() + exp();
    case '-':return exp() - exp();
    case '*':return exp() * exp();
    case '/':return exp() / exp();
    default:return atof(a);
    }
}
int main(){
    printf("%.2lf", exp());
    return 0;
}

样例：

输入：+ 5 * - 6 / 4 2 3
输出：17.00

参考博客：https://blog.csdn.net/yuanlaijike/article/details/82346369
本文尚不成熟，日后将做补充
——2020.3.14