洛谷P1175 表达式的转换题解

题意：

平常我们书写的表达式称为中缀表达式，因为它将运算符放在两个操作数中间，许多情况下为了确定运算顺序，括号是不可少的，而后缀表达式就不必用括号了。

后缀标记法：书写表达式时采用运算紧跟在两个操作数之后，从而实现了无括号处理和优先级处理，使计算机的处理规则简化为：从左到右顺序完成计算，并用结果取而代之。

例如：8-(3+2*6)/5+4 可以写为：8 3 2 6 * + 5 / - 4 +

其计算步骤为：
8 3 2 6 * + 5 / - 4 +
8 3 12 + 5 / - 4 +
8 15 5 / - 4 +
8 3 - 4 +
5 4 +
9
编写一个程序，完成这个转换，要求输出的每一个数据间都留一个空格。

输入格式：

就一行，是一个中缀表达式。输入的符号中只有这些基本符号 0123456789+-*/^()，并且不会出现形如 2*-3 的格式。

表达式中的基本数字也都是一位的，不会出现形如 12 形式的数字。

所输入的字符串不要判错。

输出格式：

若干个后缀表达式，第 $i + 1$ 行比第 $i$ 行少一个运算符和一个操作数，最后一行只有一个数字，表示运算结果。

提示\&数据范围：

运算的结果可能为负数，/ 以整除运算。并且中间每一步都不会超过 $2^{31}$。字符串长度不超过 $100$。

注意乘方运算 ^ 是从右向左结合的，即 2 ^ 2 ^ 3 为 2 ^ (2 ^ 3)，后缀表达式为 2 2 3 ^ ^。

其他同优先级的运算是从左向右结合的，即 4 / 2 / 2 * 2 为 ((4 / 2) / 2) * 2，后缀表达式为 4 2 / 2 / 2 *。

保证不会出现计算乘方时幂次为负数的情况，故保证一切中间结果为整数。

发现自己还没写过中缀表达式转后缀表达式的板子。

依次考虑每一字符，同时维护一个符号栈：

若 $c_i$ 是数字，直接输出。
若 $c_i$ 是 ( ，直接入栈即可。
若 $c_i$ 是 ) ，则依次取出栈顶并输出，直到遇到第一个 ( 并弹出它（不输出）
若 $c_i$ 是 ^ ，直接入栈即可，可以发现不影响最后的答案。
若 $c_i$ 为 +-*/ 之一，则依次取出栈顶并输出，直到遇到第一个优先级严格小于 $c_i$ 的，并将 $c_i$ 入栈

至于后缀表达式的计算，这应该大家都会吧（

时间复杂度 $\mathcal{O}(n^2)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
typedef pair<int,int> pii;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(115))
#define Fi first
#define Se second

int qpow(int a,int b)
{
    int r = 1;
    while(b) {
        if(b & 1) r = r * a;
        b >>= 1; a = a * a;
    }
    return r;
}
vector<pii> vec; stack<char> op; stack<int> s,t;
void print1()
{
    int l = vec.size();
    for(int i = 0; i < l; i++)
    {
        if(vec[i].Fi) cout << vec[i].Se << " \n"[i == l - 1];
        else cout << (char)vec[i].Se << " \n"[i == l - 1];
    }
}
void print2(int x)
{
    int l = vec.size();
    while(!s.empty()) { t.push(s.top()); s.pop(); }
    while(!t.empty()) { cout << t.top() << ' '; s.push(t.top()); t.pop(); }
    for(int i = x; i < l; i++)
    {
        if(vec[i].Fi) cout << vec[i].Se << ' ';
        else cout << (char)vec[i].Se << ' ';
    }
    cout << '\n';
}
int getp(char c)
{
    if(c == '^') return 3;
    if(c == '*' || c == '/') return 2;
    if(c == '+' || c == '-') return 1;
    if(c == '(' || c == ')') return 0;
    return -1;
}
int n; char c[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> (c + 1); n = strlen(c + 1);
    for(int i = 1; i <= n; i++)
    {
        if(isdigit(c[i])) { vec.push_back({1, c[i] ^ 48}); }
        else
        {
            if(c[i] == '(') op.push(c[i]);
            else if(c[i] == ')') {
                for(; op.top() != '('; op.pop()) { vec.push_back({0, op.top()}); }
                op.pop();
            }else if(c[i] == '^') op.push(c[i]);
            else {
                for(; !op.empty() && getp(op.top()) >= getp(c[i]); op.pop()) { 
                    vec.push_back({0, op.top()});
                } op.push(c[i]);
            }
        }
    }
    for(; !op.empty(); op.pop()) { vec.push_back({0, op.top()}); }
    print1(); int l = vec.size();
    for(int i = 0; i < l; i++)
    {
        if(vec[i].Fi) s.push(vec[i].Se);
        else
        {
            int a, b; char p = vec[i].Se;
            b = s.top(); s.pop(); a = s.top(); s.pop();
            switch (p)
            {
                case '+' : s.push(a + b); break;
                case '-' : s.push(a - b); break;
                case '*' : s.push(a * b); break;
                case '/' : s.push(a / b); break;
                case '^' : s.push(qpow(a, b)); break;
                default: break;
            }
            print2(i + 1);
        }
    }
    return 0;
}