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

前言

🚀 个人主页：阿阿阿阿锋的主页_CSDN
🔥 有问题欢迎指出，
🔥 希望能和大家一起加油，一起进步！

图片说明

@TOC

🍘介绍

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