题解 | #S-expression#

#include <bits/stdc++.h>
using namespace std;

const unordered_set<string> errors = {"Division By Zero", "Type Mismatch", "Unbound Identifier"};
const unordered_set<string> binary = {"+", "-", "*", "/", "<", ">", "="};
map<string, string> value_map;

int find(const vector<string> &words, int x) {
    if (words[x] != "(") 
        return x;
    int rest = 1, poi = x + 1;
    while (poi < words.size()) {
        if (words[poi] == "(") 
            rest ++;
        if (words[poi] == ")")
            rest --;
        if (rest == 0)
            return poi;
        poi ++;
    }
    return poi;
}

string dfs(const vector<string> &words, int x, int y) {
    if (words[x] == "(")
        return dfs(words, x + 1, y - 1);
    if (binary.count(words[x])) {
        string le = "", ri = "";
        char op = words[x][0];
        int next = x + 1;
        if (words[x + 1] == "(") {
            next = find(words, x + 1);
        }
        le = dfs(words, x + 1, next);
        if (errors.count(le))
            return le;
        ri = dfs(words, next + 1, y);
        if (errors.count(ri)) 
            return ri;
        if (le == "true" || le == "false" || ri == "true" || ri == "false")
            return "Type Mismatch";
        int leVal = stoi(le), riVal = stoi(ri);
        switch (op) {
            case '+':
                return to_string(leVal + riVal);
            case '-':
                return to_string(leVal - riVal);
            case '*':
                return to_string(leVal * riVal);
            case '/':
                if (riVal == 0)
                    return "Division By Zero";
                return to_string(leVal / riVal);
            case '<':
                return leVal < riVal ? "true" : "false";
            case '>':
                return leVal > riVal ? "true" : "false";
            case '=':
                return leVal == riVal ? "true" : "false";
            default:
                return "Error";
        }
    }
    else if (words[x] == "if") {
        int next = find(words, x + 1);
        string res = dfs(words, x + 1, next);
        if (errors.count(res))
            return res;
        if (res != "true" && res != "false")
            return "Type Mismatch";
        string value;
        next ++;
        int last = find(words, next);
        if (res == "true") {
            return dfs(words, next, last);
        }
        else {
            next = last + 1;
            last = find(words, next);
            return dfs(words, next, last);
        }
    }
    else if (words[x] == "let") {
        int next = find(words, x + 1);
        string var = words[x + 2], value = dfs(words, x + 3, next - 1);
        if (errors.count(value))
            return value;
        value_map[var] = value;
        return dfs(words, next + 1, y);
    }
    else {
        if (words[x] == "true" || words[x] == "false")
            return words[x];
        if (words[x][0] >= 'a' && words[x][0] <= 'z' && !value_map.count(words[x]))
            return "Unbound Identifier";
        return value_map.count(words[x]) ? value_map[words[x]] : words[x];
    }
}

int main() {
    int n;
    cin >> n; cin.get();
    for (int test_case = 0; test_case < n; test_case++) {
        string s, word;
        getline(cin, s);
        stringstream ss(s);
        vector<string> words;
        while(ss >> word) {
            words.push_back(word);
        }
        cout << dfs(words, 0, word.size() - 1) << endl;
    } 
}
// 64 位输出请用 printf("%lld")