前言

🚀 个人主页：清风莫追
🔥 有问题欢迎指出，
🔥 希望能和大家一起加油，一起进步！

后缀表达式

前言
🍘介绍
🍘问题分析
🍘最终代码
🍘总结

🍘介绍

所谓后缀表达式是指这样的一个表达式：式中不再引用括号，运算符是放在两个运算对象之后，所有计算按运算符号出现的顺序，严格地由左而右新进行（不用考虑运算符的优先级）。
如：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<iostream>
#include<stack>
using namespace std;
stack<char> 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<char> 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;
}
/*
测试数据
3.5.2.-*7.+@
10.28.30./*7.-6.+@
1000.1000./5.-6.*@
*/