STL模板类大法！！

pengzhaozhao · 2020-04-12 22:35:33 · 题解

STL模板类太好用了，大佬们看过来嘞！

逆波兰算法是什么我就不多说了，大佬们应该知道的，不知道的看这里：[逆波兰算法](https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/solution/ji-bai-bai-fen-bai-suan-fa- -by-19ty72/)

我们先构建这一题的基本大框架算法

读入中缀表达式，将它转成后缀表达式。
根据后缀表达式算出结果。

~~第一条有点难。~~

然后我们需要什么变量，在这里先跟大家说一下：

名为sop的栈，在中缀表达式转后缀表达式的过程中存放运算符，分界符，不存放操作数。
名为l的双端队列（deque），用来存放最终的后缀表达式。
名为scalc的栈，用来辅助计算，并且包含最终的结果。
名为recycle的双端队列，用来辅助输出。

字符串有可能不完全是操作数，也有可能是运算符（这里没有分界符）

for (i = 0; i < s.length(); i++)

1.如果是操作数，则直接压如栈l。

2 如果是分界符,

I：左括号，压入栈l，等待有括号出现。

II：右括号，while sop顶不是左括号 sop出栈并入到l里面实现运算符反转（为什么后来讲）

找到了之后丢弃左右括号。

3.如果是运算符，将新来的元素(s[i])用op1来表示，sop栈顶用op2来表示，则

I：如果op2不是运算符，则op1与op2没有可比性，op2入栈sop，continue；

II：如果是运算符，则比较优先级（加减乘在一起我要先算乘那种）

一：如果优先级大于op2，则压入栈sop（这就是为什么我在第二点说要实现运算符反转，因为栈是反的）

二：如果优先级小于等于op1，则sop出栈并push_back进l，重复第三条（因为op1没处理完）。

※最终，如果sop还有元素，则依次弹出加入l（有可能是某些优先级最大的运算符）

但没有可能是括号，因为括号已经在第二条中匹配完了并且丢弃了。

接下来，我们就要开始给deque赋值了，关于这个加减乘除乘方的问题，我是说这么解决的：

如果是+，那就是LONG_LONG_MAX-4；//LONG_LONG_MAX是long long 的最大值

如果是-，那就是LONG_LONG_MAX-3；

如果是*，那就是LONG_LONG_MAX-2；

如果是/，那就是LONG_LONG_MAX-1；留点白是好事。

3.在那个双头队列l中，如果l.front()是数字，则直接push到scalc中，如果是大于INT_MAX(int最大值)的，那说明是运算符，那我就把scalc中的上面两个元素出栈，并赋值给num1, num2，再把他们抛给计算函数（自定义），

注意，如果是减法和除法那得反过来，scalc栈出栈顺序是相反的！我们要把算出来的结果再压回给scalc栈，方便下一次遇到运算符运算。

以此类推，最终scalc.top()就是最终结果！

好，BB了这么多，终于上代码了！

#include <bits/stdc++.h>
using namespace std;
string s;
stack<char> sop;
stack<int> scalc;
deque<char> l;
deque<long long> recycle;

void print(deque<char>, deque<long long>);
void Cal();
int com(char);
void op(int, int, char);
void Turn_houzhui();

int com(char c)
{
    if (c == '+' or c == '-') return 1;
    if (c == '*' or c == '/') return 2;
    if (c == '^') return 3;
    return 0;
}
void Turn_houzhui()
{
    for (int i = 0; i < s.length(); i++)
    {
        if (s[i] >= '0' and s[i] <= '9') l.push_back(s[i]);
        else
        {
            if (s[i] == '(' or s[i] == ')')
            {
                if (s[i] == '(') sop.push(s[i]);
                else
                {
                    while (sop.top() != '(')
                    {
                        l.push_back(sop.top());
                        sop.pop();
                    }
                    sop.pop();
                }
            }
            else
            {
                if (sop.empty() or sop.top() == '(')
                {
                    sop.push(s[i]);
                    continue;
                }
                while (com(s[i]) <= com(sop.top()))
                {
                    l.push_back(sop.top());
                    sop.pop();
                    if (sop.empty() or sop.top() == '(')
                    {
                        sop.push(s[i]);
                        break;
                    }
                    else {
                        if (com(s[i]) > com(sop.top()))
                        {
                            sop.push(s[i]);
                            goto WAI;
                        }
                    }
                }
                if (com(s[i]) > com(sop.top())) sop.push(s[i]);
                WAI : continue;
            }
        }
    }
    while (not sop.empty())
    {
        l.push_back(sop.top());
        sop.pop();
    }
    return;
}
void op(int a, int b, char c)
{
    if (c == '+')
    {
        scalc.push(a + b);
        recycle.push_back(a + b);
    }
    if (c == '-')
    {
        scalc.push(a - b);  
        recycle.push_back(a - b);
    }
    if (c == '*')
    {
        scalc.push(a * b);  
        recycle.push_back(a * b);
    }
    if (c == '/')
    {
        scalc.push(a / b);
        recycle.push_back(a / b);
    } 
    if (c == '^')
    {
//      cout << a << " " << b << endl;
        long long temp = a;
        for (int i = 1; i < b; i++) a *= temp;
        scalc.push(a);
//      cout << "a:" << a << endl;2
        recycle.push_back(a);
    }
    return;
}
void print(deque<char> l, deque<long long> recycle)
{
    while (not recycle.empty())
    {
        if (recycle.front() > INT_MAX)
        {
            if (recycle.front() == LONG_LONG_MAX - 4) cout << '+' << ' ';
            else if (recycle.front() == LONG_LONG_MAX - 3) cout << '-' << ' ';
                 else if (recycle.front() == LONG_LONG_MAX - 2) cout << '*' << ' ';
                      else if (recycle.front() == LONG_LONG_MAX - 1) cout << '/' << ' ';
                           else cout << '^';
        }
        else cout << recycle.front() << ' ';
        recycle.pop_front();
    }
    while (not l.empty())
    {
        cout << l.front() << ' ';
        l.pop_front();
    }
    cout << endl;
    return;
}
void test (deque<char> x)
{
    while (not x.empty())
    {
        cout << x.front() << ' ';
        x.pop_front();
    }
    cout << endl;
    return;
}
void Cal()
{
    int num1 = 0, num2 = 0;
    test(l);
    while (not l.empty())
    {
        bool calcu = false;
        if (l.front() >= '0' and l.front() <= '9') scalc.push(l.front() - '0');
        else if (l.front() == '+' or l.front() == '-' or l.front() == '*' or l.front() == '/' or l.front() == '^')
        {
            num1 = scalc.top(); scalc.pop();
            num2 = scalc.top(); scalc.pop();
            recycle.pop_back(); recycle.pop_back();
            calcu = true;
            if (l.front() == '+' or l.front() == '*') op(num1, num2, l.front());
            else op(num2, num1, l.front());
        }
        if ((l.front() < '0' or l.front() > '9') and calcu == false) {
            if (l.front () == '+') recycle.push_back(LONG_LONG_MAX - 4);
            else if (l.front() == '-') recycle.push_back(LONG_LONG_MAX - 3);
                 else if (l.front () == '*') recycle.push_back(LONG_LONG_MAX - 2);
                      else if (l.front() == '/') recycle.push_back(LONG_LONG_MAX - 1);
                           else recycle.push_back(LONG_LONG_MAX);
        }
        else if (calcu == false) recycle.push_back(l.front() - '0');
        l.pop_front();
        if (calcu) print(l, recycle);
    }
    scalc.pop();
    return;
}
int main ()
{
    getline(cin, s);
    Turn_houzhui();
    Cal();
    return 0;
}