一道表达式模拟题

题目

现有一个被压缩的字符串（有小写字母、括号、数字组成），压缩规则如下所示。

压缩后：

2(2u2lt4d)3(rb)pa

压缩前：

uulltdddduulltddddrbrbrbpa

现给定压缩后的字符串，求26个小写字母在源字符串中分别出现的次数。你可以假设输入是合法的。

数据范围：

设N为压缩后的字符串长度，M为压缩前的字符串长度。

1 <= N <= 1000

1 <= M <= 2^60

思考

本质上是模拟一个计算器。

lc224.基本计算器

2(2u2lt4d)3(rb)pa相当于(2*(2*u+2*l+t+4*d)+3*(r+b)+p+a). 这里整个表达式外面再套一对括号是避免最后再evaluate的情况（比如到最后剩下2*a就还得calc一次，但(2*a)在碰到最后一个)的时候就会把2*a算掉）。

用map<char, int>储存字母出现的次数。

这题比224难的点在于: 1. 有乘号，所以要考虑优先级；2. 操作数有数字和map两种类型。

难点解析

优先级

只要在碰到“+”号的时候把前面的“*”号都evaluate掉就可以了。

操作数类型

乘法运算定义为：number * map (map中所有频率 *= number)

加法运算定义为：map + map (对应字母的频率加起来)

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <map>
#include <unordered_set>
#include <set>
#include <vector>
#include <queue>
#include <numeric>
#include <stack>
using namespace std;
using LL = long long;

string in;

bool isNum(char c) {
    return '0' <= c && c <= '9';
}
bool isAlpha(char c) {
    return 'a' <= c && c <= 'z';
}

void calc(stack<LL>& nums, stack<unordered_map<char, LL>>& maps, stack<char>& ops) {
    if (ops.top() == '*') {
        auto m = maps.top(); maps.pop();
        auto num = nums.top(); nums.pop();
        for (auto& [_, v] : m) v *= num;
        maps.push(m);
    } else {
        auto m1 = maps.top(); maps.pop();
        auto m2 = maps.top(); maps.pop();
        for (auto [k, v] : m2) m1[k] += v;
        maps.push(m1);
    }
    ops.pop();
}

void solve() {
    int n = in.size();
    string s = "(";
    for (int i = 0; i < n; i++) {
        char c = in[i];
        if (isAlpha(c)) {
            if (i && isNum(in[i - 1])) {
                s += '*';
            }
            if (i && (isAlpha(in[i - 1]) || in[i - 1] == ')')) {
                s += '+';
            }
            s += c;
        }
        else if (isNum(c)) {
            if (i && in[i - 1] != '(' && !isNum(in[i - 1])) s += '+';
            s += c;
        }
        else if (c == '(') {
            s += '*'; s += c;
        }
        else s += c;
    }
    s += ")";
    // cout << s << endl;
    string buffer;
    stack<LL> nums;
    stack<unordered_map<char, LL>> maps;
    stack<char> ops;

    for (char c : s) {
        if (isNum(c) || isAlpha(c)) {
            buffer += c;
        } else if (!buffer.empty()) {
            if (isNum(buffer[0]))
                nums.push(stoll(buffer));
            else {
                unordered_map<char, LL> tmp;
                for (char cc : buffer) tmp[cc] += 1;
                maps.push(tmp);
            }
            buffer = "";
        }
        if (c == '(') {
            ops.push('(');
        } else if (c == '+') {
            while (ops.top() != '(') {
                calc(nums, maps, ops);
            }
            ops.push('+');
        }
        else if (c == '*') ops.push('*');
        else if (c == ')'){
            while (ops.top() != '(') {
                calc(nums, maps, ops);
            }
            ops.pop();
        }
    }
    //cout << maps.empty();

    auto m = maps.top();
    for (char c = 'a'; c <= 'z'; c++) {
        cout << c << ' ' << m[c] << endl;
    }

}
int main(){
    // 自分の得意な言語で
    // Let's チャレンジ！！
    cin >> in;
    solve();
    return 0;
}

优化

map可以换成长度为26的vector。

总结

计算器类题目的要点：

1. 双栈储存操作数和操作符。
2. 用buffer来储存未读取完的操作数。
3. 用calc函数抽象出运算操作。
4. 在整个表达式外面套一对括号可以起到“哨兵”的作用，减少特殊判断。