计算后缀表达式-算法与数据结构-栈的运用-C++语言实现

• 介绍
• 问题分析
• • 思路
  • 一些细节和问题
  • • 一、数据类型处理
    • 二、负数
• 最终代码
• 总结

所谓后缀表达式是指这样的一个表达式：式中不再引用括号，运算符是放在两个运算对象之后，所有计算按运算符号出现的顺序，严格地由左而右新进行（不用考虑运算符的优先级）。
如：3*(5–2)+7对应的后缀可以表达式为：3．5．2．-*7．+@。’@’为表达式的结束符号。‘.’为操作数的结束符号。
后缀表达式的一个特点就是方便计算。
我们下面只考虑 加减乘除 四种基本运算，以及表达式中没有 负数 的情况。

那么我们如何计算一个后缀表达式呢？
可以借用栈来实现。
此外，后缀表达式也可以用一个二叉树来表示和计算，但是我们这里就不细讲啦！

我们先抛开问题中一些具体的细节（如：是用‘.’作为操作数的结束符号），方便理清对于整个问题的一个思路。
还是用之前那个例子：
3．5．2．-*7．+@
我们从后缀表达式左边开始一边读取数据一边压入栈中，当遇到了运算符时，就将栈中的操作符以及紧邻的两个操作数出栈进行相应的运算，运算结果压入栈中作为新的操作数，然后继续从表达式中读取数据。反复进行以上操作直到得到运算结果。
过程如下图：

在了解了一个大概的思路之后，我们就需要考虑程序实现中的一些细节问题了。

一个后缀表达式中有操作数这样的数字，也有运算符这样的符号，所以最终是以博主都用char类型进行存储的。
那么我们如何从以char类型存储了部分表达式的栈中，将操作数和运输符分别读取出来进行运算呢？
需要注意，我们在压入栈中时，是一个字符一个字符的压的，所以在栈中的多位数是倒过来的，如：123压入栈中从栈顶开始看就是321。
下面是从栈中读取出一个操作数的代码段：

//从char型栈中读取出一个int型操作数 
int get_num() {
	int sum(0);
	for(int i = 1; s.top() != '.'; i *= 10) {
		sum += (int)(s.top() - '0') * i;
		s.pop();
		if(s.empty()) break;
	}
	return sum;
}

虽然我们前面说了不考虑表达式中有负数的情况，但是在对表达式的计算过程中仍然可能会产生负数，不过这种情况对于博主来说稍稍好处理一点（读取表达式时，负数的负号与减法运算符相同，有歧义）。
博主处理运算过程中负数的方法是，先压入一个字符0作为符号标记，然后将原数的相反数（就是一个非负数了）压入栈中。在出栈时如果数字串的最后一个是0，就将数据取相反数，重新得到原来的负数。

#include
#include
using namespace std;
stack s;
int get_num();		//从栈中返回一个整型数字 
int main(){
	char t(0);
	while(true) {
		//输入 
		cin >> t;
		if(t == '@') {
			s.pop();
			cout << get_num();
			break;
		}
		s.push(t);
		
		//见运算符
		if(t == '+' || t == '-' || t == '*' || t == '/') {
			//出栈运算符
			s.pop();
			//出栈两个数字为int型
			int a(0), b(0);
			s.pop();
			a = get_num();
//			cout << "a = " << a << endl;
			s.pop();
			b = get_num();
//			cout << "b = " << b << endl;
			//计算 
			int result(0);
			if(t == '+') result = b + a;
			else if(t == '-') result = b - a;
			else if(t == '*') result = b * a;
			else if(t == '/') result = b / a;
//			cout << "result = " << result << endl;
			if(result < 0) {
				s.push('0'); 
				result = -result;
//				cout << "result = " << result << endl;
			}
			//结果转为char型再入栈
			stack c;
			if(result == 0) {
				s.push('0');
			}
			while(result != 0) {
				c.push((char)(result % 10 + '0'));
				result /= 10;
			}
			while(!c.empty()) {
				s.push(c.top());
				c.pop();
			}
			s.push('.');
		}
	}
}
//------------------------------
//从char型栈中读取出一个int型操作数 
int get_num() {
	int sum(0);
	char t(0);
	for(int i = 1; s.top() != '.'; i *= 10) {
		t = s.top();
		sum += (int)(s.top() - '0') * i;
		s.pop();
		if(s.empty()) break;
	}
	if(t == '0') sum = -sum;
	return sum;
}

后缀表达式是一个比较经典的问题。栈的原理其实很简单，就像一个加了限制的数组，只能从同一端进出数据。
但是在用栈解决一些问题时，你会发现它真的好神奇，也许这就是数据结构和算法的魅力吧！

博主水平有限，欢迎来评论区交流和指正。

你们的支持，就是博主不断创作的动力，如果文章能对你们有一些小小的帮助，就来个三连叭（点赞收藏加关注哦）！