p1175题解

· · 题解

蒟蒻的第一篇题解，请多多关照。

前言

这个题目 dalao 们有的是用二叉树之类的做的，因为我一个蒟蒻，所以我只好使用 if else 之类的代码来模拟，所以代码比较长。但是这篇题解比较适合初学者，dalao 参考一下就彳亍了。

题意

相信各位同学来到这道题一定已经了解了后缀表达式的相关知识吧！如果您还不太了解后缀表达式的相关计算，可以前往这篇文章了解一下。

这题其实有 2 个子任务：

中缀转后缀

在我刚刚给的那篇文章里已经给出了比较详细中缀转后缀的步骤。简单总结一下发现应该这样的步骤：

ps：在表达式的计算几乎全部是栈的，不过我为了输出方便，将一些栈改成了双向队列 deque 来存储，但本质还是一个栈。（下面我还是会使用“栈”代替 deque 写这篇题解）。

  1. 数字：直接进入 s2 栈。
  2. 括号：
    • 左括号 ( 直接进 s1 栈。
    • 右括号 ) 则一直弹出 s1 的运算符到 s2，直到碰到左括号 (。
  3. 运算符：一直弹出 s1 栈顶大于等于自己运算级的运算符到 s2，然后入栈。

扫描完后一直弹出 s1 剩余的运算符到 s2。

当然了，这道题也有一些恶心的地方。比如乘方 ^ 是从右向左结合的，所以这里的 ^ 直接进 s1 栈。而不用弹出栈顶和 ^ 运算级相同的运算符。

还有，因为我选择把运算符和数字存到一起，所以肯定会出现冲突的情况。题目里说了每一步不会超过 2^{31}，所以我选择开 long long。每个运算符使用一个大于 2^{31} 的数来存储，输出的时候解过来就彳亍了。

这一部分的代码：

int fh[256];
// 符号对照表 
// "m" 是2的31次方
char fh2[17]; 
string a; // 题目的字符串
stack<long long> s1;
deque<long long> s2;
deque<long long> s3;

// 初始化成后缀 
void init() {
    for (int i=0;i<a.length();i++) {
        int n=fh[a[i]];
        if (n>=0 && n<=9) s2.push_back(n);
        //是数字直接入栈 
        else {
            // 是符号 
            // (
            if (n==16) {
                s1.push(n);
                continue;
            }
            if (n==fh['^']) {
                // ^ 
                s1.push(n);
                continue;
            }
            // )
            if (n==17) {
                while (s1.top()!=16) {
                    // 一直循环直到 “(” 
                    s2.push_back(s1.top()+m);
                    // 弹出栈顶
                    s1.pop();
                }
                s1.pop();
                // 弹出 (
            } else if (n==fh['+'] || n==fh['-']) {
                // +或- 
                while (!s1.empty() && (s1.top()==fh['+'] || s1.top()==fh['-'] || s1.top()==fh['*'] || s1.top()==fh['/'] || s1.top()==fh['^'])) {
                    s2.push_back(s1.top()+m);
                    // 弹出栈顶
                    s1.pop();
                }
                s1.push(n);
            } else if (n==fh['*'] || n==fh['/']) {
                // *或/ 
                while (!s1.empty() && (s1.top()==fh['*'] || s1.top()==fh['/'] || s1.top()==fh['^'])) {
                    s2.push_back(s1.top()+m);
                    // 弹出栈顶
                    s1.pop();
                }
                s1.push(n);
            }
        }
    }
    while (!s1.empty()) {
        s2.push_back(s1.top()+m);
        s1.pop();
    }
}

输出中缀的计算过程

首先，这里的计算是要输出过程的，所以每计算一次就得等下一轮再计算。

计算简单来说，就是如果扫描到了运算符，就对栈顶的两个数弹出做运算之后再压进去。这样一直循环直到栈只剩一个元素就结束了。后缀表达式应当将栈顶的第一个元素作为第二个运算符，即减法里面的减数。栈顶的第二个元素作为第一个运算符，即减法里的被减数。

所以实现的办法是：一直循环知道 s2 只剩一个元素，然后一直把 s2 栈顶的元素弹出并压入 s3，如果 s3 栈顶的元素是运算符，则弹出 s3 栈顶的两个数做运算，然后将运算的结果压入 s3，标记变量 cal 为 true 以记录本轮计算过了。压入剩余元素，用 s3 更新 s2 并且输出栈后，进行下一轮。

这一部分的代码：

// 这个函数是判断是不是只有一个元素在栈里面
bool one(deque<long long> s) {
    s.pop_back();
    return s.empty();
}
// 计算 
void calc() {
    int i2,i1;
    while (!one(s2) && !s2.empty()) {
        while (!s3.empty()) s3.pop_back();
        // 清空s3 
        bool cal=false;
        // 算过1次就不算了 
        // 一直计算直到没了 
        while (!s2.empty()) {
            s3.push_back(s2.front());
            s2.pop_front();
            // 如果是运算符 
            long long b=s3.back();
            if (b>m+1 && !cal) {
                s3.pop_back();
                cal=true;
                // 标记算过了 
                i2=s3.back();
                s3.pop_back();
                i1=s3.back();
                s3.pop_back();
                // 分类讨论运算符
                if (b==11+m) {
                    s3.push_back(i1+i2);
                }
                if (b==12+m) {
                    s3.push_back(i1-i2);
                }
                if (b==13+m) {
                    s3.push_back((i1*i2));
                }
                if (b==14+m) {
                    s3.push_back(i1/i2);
                }
                if (b==15+m) {
                    s3.push_back(pow(i1,i2));
                }
            }
        }
        codq(s3);
        s2=s3;
        // 更新
    }
}

输出栈

当我们栈都弄好之后，就是输出的时候了。输出的话就是不断抽出队列的前端 s.front()。因为后缀是要逆序输出的，队列比较方便。输出队列的前端，就是逆序输出了。如果是运算符就将运算符解开（我用了一个数字来存）然后输出。碰到数就直接输出就行了。

这部分的代码：

// 输出双向队列 
void codq(deque<long long> s) {
    while (!s.empty()) {
        if (s.front()>m) cout << fh2[s.front()-m] << " "; else cout << s.front() << " ";
        s.pop_front();
    }
    cout << endl;
}

总结

总结一下遇到的问题吧：

  1. RE：我刚写的时候总是 RE，原因是抽栈顶的运算符要判断运算级，然后要执行一次 stack.top()，如果栈是空的，那么就会 RE，所以以后写这种一定要先判断一下栈是否不为空。
  2. 关于运算符。我后来被怎么存运算符困扰了很久。不过后来我发现其实开个 long long 不仅轻松的完成了任务，还完全不影响 MLE，所以大多数题开 long long 完全是没事的。

ps：long 是没用的！它的范围和 int 一样！

最终代码

大家最爱的代码环节！

#include <iostream>
#include <queue>
#include <stack>
#include <deque>
#include <cstring>
#include <math.h>
using namespace std;
/*
0:+
1:-
2:*
3:/
4:^
*/
int fh[256];
// 符号对照表 
char fh2[17];
string a;
stack<long long> s1;
// 初始用 
deque<long long> s2;
// 初始用 
deque<long long> s3;
// 计算用 双向队列，可以删掉前面的 , 因为运算符和数字要区分开，所以开long 
long long m;
// 2的31次方-1，存运算符 
// cout deque
// 输出双向队列 
void codq(deque<long long> s) {
    while (!s.empty()) {
        if (s.front()>m) cout << fh2[s.front()-m] << " "; else cout << s.front() << " ";
        s.pop_front();
    }
    cout << endl;
}
// 初始化成后缀 
void init() {
    for (int i=0;i<a.length();i++) {
        int n=fh[a[i]];
        if (n>=0 && n<=9) s2.push_back(n);
        //是数字直接入栈 
        else {
            // 是符号 
            // (
            if (n==16) {
                s1.push(n);
                continue;
            }
            if (n==fh['^']) {
                // ^ 
                s1.push(n);
                continue;
            }
            // )
            if (n==17) {
                while (s1.top()!=16) {
                    // 一直循环直到 “(” 
                    s2.push_back(s1.top()+m);
                    // 弹出栈顶
                    s1.pop();
                }
                s1.pop();
                // 弹出 (
            } else if (n==fh['+'] || n==fh['-']) {
                // +或- 
                while (!s1.empty() && (s1.top()==fh['+'] || s1.top()==fh['-'] || s1.top()==fh['*'] || s1.top()==fh['/'] || s1.top()==fh['^'])) {
                    s2.push_back(s1.top()+m);
                    // 弹出栈顶
                    s1.pop();
                }
                s1.push(n);
            } else if (n==fh['*'] || n==fh['/']) {
                // *或/ 
                while (!s1.empty() && (s1.top()==fh['*'] || s1.top()==fh['/'] || s1.top()==fh['^'])) {
                    s2.push_back(s1.top()+m);
                    // 弹出栈顶
                    s1.pop();
                }
                s1.push(n);
            }
        }
    }
    while (!s1.empty()) {
        s2.push_back(s1.top()+m);
        s1.pop();
    }
}
// 栈（此处我用的是队列因为输出方便）是否只有1个元素，如果只有一个那就结束了 
bool one(deque<long long> s) {
    s.pop_back();
    return s.empty();
}
// 计算 
void calc() {
    int i2,i1;
    while (!one(s2) && !s2.empty()) {
        while (!s3.empty()) s3.pop_back();
        // 清空s3 
        bool cal=false;
        // 算过1次就不算了 
        // 一直计算直到没了 
        while (!s2.empty()) {
            s3.push_back(s2.front());
            s2.pop_front();
            // 如果是运算符 
            long long b=s3.back();
            if (b>m+1 && !cal) {
                s3.pop_back();
                cal=true;
                // 标记算过了 
                i2=s3.back();
                s3.pop_back();
                i1=s3.back();
                s3.pop_back();
                // 分类讨论运算符
                if (b==11+m) {
                    s3.push_back(i1+i2);
                }
                if (b==12+m) {
                    s3.push_back(i1-i2);
                }
                if (b==13+m) {
                    s3.push_back((i1*i2));
                }
                if (b==14+m) {
                    s3.push_back(i1/i2);
                }
                if (b==15+m) {
                    s3.push_back(pow(i1,i2));
                }
            }
        }
        codq(s3);
        s2=s3;
        // 更新
    }
}
int main() {
    m=pow(2,31)-1;
    // 建表 
    fh['+']=11;
    fh['-']=12;
    fh['*']=13;
    fh['/']=14;
    fh['^']=15;
    fh['(']=16;
    fh[')']=17;
    fh2[11]='+';
    fh2[12]='-';
    fh2[13]='*';
    fh2[14]='/';
    fh2[15]='^';
    for (int i=0;i<=9;i++) {
        fh[i+'0']=i;
        fh2[i]=i+'0';
    }
    cin >> a;
    init();
    // 输出第一轮 
    codq(s2);
    calc();
    return 0;
}