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

• 速览
• 前缀表达式
• • 前缀表达式的运算规则
  • 中缀表达式转换为前缀表达式
• 后缀表达式
• • 后缀表达式的运算
  • 中缀表达式转换为后缀表达式

算术表达式分为：

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

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

(2 + 3) * 4 - 5

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

- * + 2 3 4 5

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

+ - 1 2 * 3 5

也可以是前缀表达式

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

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

前缀表达式的值为 15

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

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

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

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

代码实现：

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

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

int main(int argc, char*argv[]) {
	// 输入中缀表达式
	string infix;
	cin >> infix;
	// 中缀表达式 => 前缀表达式
	stackS1, 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();
	}
	// 计算前缀表达式的值
	stackvalue;
	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;
}

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

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

后缀表达式的值为 15

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

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

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

所求后缀表达式为：1 2 3+4*+5-

代码实现：

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

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

int main(int argc, char*argv[]) {
	// 输入中缀表达式
	string infix;
	cin >> infix;
	// 中缀表达式 => 后缀表达式
	stackS1, S2;
	for (auto it = infix.cbegin(); it != infix.cend(); 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()) && ('*' == *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.insert(prefix.begin(), S2.top());
		S2.pop();
	}
	// 计算后缀表达式的值
	stackvalue;
	for (auto it = prefix.cbegin(); it != prefix.cend(); 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(second_top + top); break;
			case'-':value.push(second_top - top); break;
			case'*':value.push(second_top*top); break;
			case'/':value.push(second_top / 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;
}

优化代码：
// 后缀表达式求值
#include
using std::cin;
using std::cout;
using std::endl;
#include
using std::string;
#include
using std::stack;

bool isop(char _C);
void orgnize(string&str);

int main() {
	string input, buffer;
	while (!cin.eof()) {
		cin >> buffer;
		input.append(buffer);
		input.push_back(32);
		buffer.clear();
	}
	orgnize(input);
	stackvalue;
	for (auto it = input.begin(); it != input.end();) {
		if (isdigit(*it)) {
			while (isdigit(*it))
				buffer.push_back(*it++);
			value.push(atoi(buffer.c_str()));
			buffer.clear();
		}
		else if (isop(*it)) {
			int top, second_top;
			top = value.top();
			value.pop();
			second_top = value.top();
			value.pop();
			switch (*it++) {
			case'+':value.push(second_top + top); break;
			case'-':value.push(second_top - top); break;
			case'*':value.push(second_top * top); break;
			case'/':value.push(second_top / top); break;
			}
		}
		else it++;
	}
	cout << "postfix(" << input << ")=" << value.top() << endl;
	return 0;
}

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

void orgnize(string&str) {
	while (!str.empty())
		if (isspace(*str.rbegin()))str.pop_back();
		else break;
	while (!str.empty())
		if (isspace(*str.begin()))str.erase(str.begin());
		else break;
	for (auto it = str.begin(); it != str.end();)
		if (isspace(*it++))
			while (isspace(*it))it = str.erase(it);
	for (auto it = str.begin(); it != str.end() - 1; it++) {
		if (isdigit(*it) && isop(it[1]))
			it = str.insert(it + 1, 32);
		else if (isop(*it) && (isdigit(it[1]) || isop(it[1])))
			it = str.insert(it + 1, 32);
	}
}

// 中缀 - 后缀转换
// infix to postfix
#include
using std::cin;
using std::cout;
using std::ostream;
using std::endl;
#include
using std::string;
#include
using std::stack;
#include
using std::vector;

struct CharInt {
	bool ischar;
	int charint;
	CharInt(bool isch, int chint) :ischar(isch), charint(chint) {}
};
ostream&operator<<(ostream&output, CharInt x) {
	if (x.ischar)output << static_cast(x.charint);
	else output << x.charint;
	return output;
}

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

int main() {
	char buffer[128];
	cin.getline(buffer, sizeof(buffer));
	stackS1;
	stackS2;
	for (auto it = buffer; *it;) {
		if (isdigit(*it)) {
			string temp;
			while (isdigit(*it))
				temp.push_back(*it++);
			S2.push(CharInt(false, atoi(temp.c_str())));
		}
		else if (isop(*it)) {
		CASE_ISOP:
			if (S1.empty() || '(' == S1.top())S1.push(*it);
			else if (('+' == S1.top() || '-' == S1.top()) && ('*' == *it || '/' == *it))
				S1.push(*it);
			else {
				S2.push(CharInt(true, S1.top()));
				S1.pop();
				goto CASE_ISOP;
			}
			it++;
		}
		else if ('(' == *it)S1.push(*it++);
		else if (')' == *it++) {
			while (S1.top() != '(') {
				S2.push(CharInt(true, S1.top()));
				S1.pop();
			}
			S1.pop();
		}
	}
	while (!S1.empty()) {
		S2.push(CharInt(true, S1.top()));
		S1.pop();
	}
	vectoroutput;
	while (!S2.empty()) {
		output.insert(output.begin(), S2.top());
		S2.pop();
	}
	for (auto it : output)
		cout << it << ' ';
	cout.put(10);
	return 0;
}