栈的应用：表达式求值

Contents

1. 0. 例题
2. 1. 分析
3. 2. 中缀表达式转换为后缀表达式
4. 3. 根据后缀表达式求值
5. 4. 测试主函数

0. 例题

编写一个程序可以完成基本的带括号的四则运算。其中除法(/)是整除，并且在负数除法时向0取整。(C/C++/Java默认的除法就是向0取整，python默认的是向负无穷取整)。
例如计算 100 * ( 2 + 12 ) - (20 / 3) * 2, 结果是1388。
样例输入：
100*(2+12)-(20/3)*2
样例输出：
1388

1. 分析

中缀表达式将二元运算符放在两个操作数之间，而后缀表达式的每个运算符都出现在相应操作数之后。后缀表达式去掉了括号，因此在计算机中，用后缀表达式求值更为简单。
100*(2+12)-(20/3)*2为中缀表达式，其对应的后缀表达式(逆波兰式)为100&2&12+*20&3/2*-。
用用后缀表达式求值是栈的典型应用，其步骤分为两步：

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

数字：直接添加到后缀表达式中，数值之间需要添加分隔符。
左括号：直接压入到符号栈。
右括号：右括号总是不入栈，遇到右括号，则之前入栈的运算符逐一出栈，并添加到后缀表达式中，直到碰到左括号。遇到左括号直接将其弹出即可。
运算符：运算符入栈之前，与符号栈栈顶的运算符比较优先级，如果优先级小于或等于栈顶运算符优先级，则栈顶运算符弹出，并添加到后缀表达式中，最后将待入栈的运算符入栈（优先级比较时，左括号当作低优先级运算符处理）。
中缀表达式循环一遍之后，最后将符号栈中的运算符逐一弹出，添加到后缀表达式中。

利用后缀表达式求值

数字：根据分隔符取出完整数值，压入到数值栈。数字处理注意如何将数字组合成完整的数值。
运算符：弹出数值栈的栈顶前两个数值，与运算符一起进行四则运算，再将运算结果压入到数值栈，当到达后缀表达式末端时，数值栈中应该只有一个数值，该值即为整个表达式的运算结果。运算符处理时，注意除法中操作数的顺序。

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

//获取运算符优先级
int getRink(char opt){    
	if (opt == '+' || opt == '-') return 10;
	if (opt == '*' || opt == '/') return 20;
	if (opt == '(') return 0;
	else return -1;
}
//中缀表达式转为后缀表达式
//str_mid:中缀表达式
//str_post:后缀表达式
int postfix(string &str_post, string &str_mid){  
	stack<char> opt;   //定义运算符栈
	bool flag = false; //标记上一个输出是否为数字
	while (!opt.empty()) opt.pop();//运算符栈清空
	for (int i = 0; str_mid[i] != '\0'; i++){
		// 数字处理
		if (str_mid[i] >= '0' && str_mid[i] <= '9'){
			if (flag) str_post += '&'; //上一个输出为数字则中间用&分隔
			else flag = true;
			//获取一个数值中的连续多个数字
			while ('0' <= str_mid[i] && '9' >= str_mid[i]){
				str_post += str_mid[i];
				i++;
			}
			i--;
		}
		//左括号处理
		else if (str_mid[i] == '('){
			opt.push(str_mid[i]);

		}
		//右括号处理
		else if (str_mid[i] == ')'){
			while (opt.top() != '(' && !opt.empty()){
				str_post += opt.top();
				opt.pop();
				flag = false;
			}
			if (opt.empty()) return -1;
			if (opt.top() == '('){
				opt.pop();
			}

		}
		//运算符处理
		else if (str_mid[i] == '+' || str_mid[i] == '-' || str_mid[i] == '*' || str_mid[i] == '/'){
			int a1 = getRink(str_mid[i]);
			if (a1<0) return -1;
			int a2;
			while (!opt.empty()){
				a2 = getRink(opt.top());
				if (a2<0) return -1;
				if (a1 <= a2){ //等于的时候也要弹出
					str_post += opt.top();
					opt.pop();
					flag = false;
				}
				else break;
			}
			opt.push(str_mid[i]);

		}
		else return -1;
	}
	// 运算符出栈
	while (!opt.empty()){
		if (opt.top() == '(') return -1;
		str_post += opt.top();
		opt.pop();
	}
	return 0;
}

3. 根据后缀表达式求值

//加减乘除结果计算
int getResult(int a, int b, char opp){
	if (opp == '+') return a + b;
	if (opp == '-') return a - b;
	if (opp == '*') return a*b;
	if (opp == '/') return a / b;
}

int compute(string str){
	stack<int>  data;
	int temp, op1, op2;
	while (!data.empty()) data.pop();
	for (int i = 0; str[i] != '\0'; i++){
		//数值分隔符直接跳过
		if ('&' == str[i]) continue;
		//数值处理
		else if ('0' <= str[i] && '9' >= str[i]) {
			temp = 0;
			while ('0' <= str[i] && '9' >= str[i]){
				temp = temp * 10 + str[i] - '0';
				i++;
			}
			i--;
			data.push(temp);
		}
		//运算符处理
		else if (str[i] == '+' || str[i] == '-' || str[i] == '*' || str[i] == '/'){
			if (data.size()<2){ return -1; }
			op1 = data.top(); data.pop();
			op2 = data.top(); data.pop();
			temp = getResult(op2, op1, str[i]); //除法的时候注意数值顺序
			data.push(temp);
		}
		else return -1;
	}
	if (data.size() != 1){
		return -1;
	}
	return data.top();
}

4. 测试主函数

int main(){
	string str_post, str_mid;
	cin >> str_mid;
	if(!postfix(str_post, str_mid)){
	  cout << str_post << endl;
	  cout << compute(str_post) << endl;
 	}
	return 0;
}