736.Lisp语法解析

链接：736.Lisp语法解析
难度：Hard
标签：栈、递归、哈希表、字符串
简介：给你一个类似 Lisp 语句的字符串表达式 expression，求出其计算结果。

题解 1 - cpp

• 编辑时间：2022-07-06
• 执行用时：32ms
• 内存消耗：26MB
• 编程语言：cpp
• 解法介绍：递归比较，每次存储当前变量。

class Solution {
   public:
    vector<unordered_map<string, int>> varStark;
    int evaluate(string expression) {
        if (expression[0] == '(')
            expression = expression.substr(1, expression.size() - 2);
        vector<string> list = toToken(expression);
        return comp(list);
    }
    vector<string> toToken(string &expression) {
        vector<string> list;
        int i;
        if (expression[0] == 'l') list.push_back("let"), i = 4;
        if (expression[0] == 'm') list.push_back("mult"), i = 5;
        if (expression[0] == 'a') list.push_back("add"), i = 4;
        while (i < expression.size()) {
            int end = expression[i] == '(' ? findEndIdx1(expression, i)
                                           : findEndIdx2(expression, i);
            list.push_back(expression.substr(i, end - i));
            i = end;
            while (i < expression.size() && expression[i] == ' ' ||
                   expression[i] == ')')
                i++;
        }
        return list;
    }
    int comp(vector<string> &list) {
        int ans;
        if (list[0] == "let") ans = comp_let(list);
        if (list[0] == "add") ans = comp_var(list[1]) + comp_var(list[2]);
        if (list[0] == "mult") ans = comp_var(list[1]) * comp_var(list[2]);
        return ans;
    }
    int comp_let(vector<string> &list) {
        int n = list.size();
        unordered_map<string, int> m;
        for (int i = 1; i < n - 1; i += 2) {
            int val;
            varStark.push_back(m);
            if (list[i + 1][0] == '(')
                val = evaluate(list[i + 1]);
            else
                val = get_var(list[i + 1]);
            varStark.pop_back();
            m[list[i]] = val;
        }
        int val;
        varStark.push_back(m);
        if (list[n - 1][0] == '(') {
            val = evaluate(list[n - 1]);
        } else
            val = get_var(list[n - 1]);
        varStark.pop_back();
        return val;
    }
    int comp_var(string &str) {
        int val;
        if (str[0] == '(')
            val = evaluate(str);
        else
            val = get_var(str);
        return val;
    }
    int get_var(string &str) {
        for (int i = varStark.size() - 1; i >= 0; i--)
            if (varStark[i].count(str)) return varStark[i][str];
        return stoi(str);
    }
    int findEndIdx1(string &expression, int start) {
        int end = start, deep = 0;
        do {
            if (expression[end] == '(')
                deep++;
            else if (expression[end] == ')')
                deep--;
            end++;
        } while (deep > 0);
        return end;
    }
    int findEndIdx2(string &expression, int start) {
        int end = start;
        while (end < expression.size() && expression[end] != ' ') end++;
        return end;
    }
};

题解 2 - cpp

• 编辑时间：2022-07-06
• 执行用时：32ms
• 内存消耗：26MB
• 编程语言：cpp
• 解法介绍：递归比较，每次存储当前变量。

class Solution {
   public:
    vector<unordered_map<string, int>> varStark;
    int evaluate(string expression) {
        if (expression[0] == '(')
            expression = expression.substr(1, expression.size() - 2);
        vector<string> list = toToken(expression);
        return comp(list);
    }
    vector<string> toToken(string &expression) {
        vector<string> list;
        int i;
        if (expression[0] == 'l') list.push_back("let"), i = 4;
        if (expression[0] == 'm') list.push_back("mult"), i = 5;
        if (expression[0] == 'a') list.push_back("add"), i = 4;
        while (i < expression.size()) {
            int end = expression[i] == '(' ? findEndIdx1(expression, i)
                                           : findEndIdx2(expression, i);
            list.push_back(expression.substr(i, end - i));
            i = end;
            while (i < expression.size() && expression[i] == ' ' ||
                   expression[i] == ')')
                i++;
        }
        return list;
    }
    int comp(vector<string> &list) {
        int ans;
        if (list[0] == "let") ans = comp_let(list);
        if (list[0] == "add") ans = comp_var(list[1]) + comp_var(list[2]);
        if (list[0] == "mult") ans = comp_var(list[1]) * comp_var(list[2]);
        return ans;
    }
    int comp_let(vector<string> &list) {
        int n = list.size();
        unordered_map<string, int> m;
        for (int i = 1; i < n - 1; i += 2) {
            int val;
            varStark.push_back(m);
            if (list[i + 1][0] == '(')
                val = evaluate(list[i + 1]);
            else
                val = get_var(list[i + 1]);
            varStark.pop_back();
            m[list[i]] = val;
        }
        int val;
        varStark.push_back(m);
        if (list[n - 1][0] == '(') {
            val = evaluate(list[n - 1]);
        } else
            val = get_var(list[n - 1]);
        varStark.pop_back();
        return val;
    }
    int comp_var(string &str) {
        int val;
        if (str[0] == '(')
            val = evaluate(str);
        else
            val = get_var(str);
        return val;
    }
    int get_var(string &str) {
        for (int i = varStark.size() - 1; i >= 0; i--)
            if (varStark[i].count(str)) return varStark[i][str];
        return stoi(str);
    }
    int findEndIdx1(string &expression, int start) {
        int end = start, deep = 0;
        do {
            if (expression[end] == '(')
                deep++;
            else if (expression[end] == ')')
                deep--;
            end++;
        } while (deep > 0);
        return end;
    }
    int findEndIdx2(string &expression, int start) {
        int end = start;
        while (end < expression.size() && expression[end] != ' ') end++;
        return end;
    }
};

题解 3 - cpp

• 编辑时间：2022-07-06
• 执行用时：32ms
• 内存消耗：26MB
• 编程语言：cpp
• 解法介绍：递归比较，每次存储当前变量。

class Solution {
   public:
    vector<unordered_map<string, int>> varStark;
    int evaluate(string expression) {
        if (expression[0] == '(')
            expression = expression.substr(1, expression.size() - 2);
        vector<string> list = toToken(expression);
        return comp(list);
    }
    vector<string> toToken(string &expression) {
        vector<string> list;
        int i;
        if (expression[0] == 'l') list.push_back("let"), i = 4;
        if (expression[0] == 'm') list.push_back("mult"), i = 5;
        if (expression[0] == 'a') list.push_back("add"), i = 4;
        while (i < expression.size()) {
            int end = expression[i] == '(' ? findEndIdx1(expression, i)
                                           : findEndIdx2(expression, i);
            list.push_back(expression.substr(i, end - i));
            i = end;
            while (i < expression.size() && expression[i] == ' ' ||
                   expression[i] == ')')
                i++;
        }
        return list;
    }
    int comp(vector<string> &list) {
        int ans;
        if (list[0] == "let") ans = comp_let(list);
        if (list[0] == "add") ans = comp_var(list[1]) + comp_var(list[2]);
        if (list[0] == "mult") ans = comp_var(list[1]) * comp_var(list[2]);
        return ans;
    }
    int comp_let(vector<string> &list) {
        int n = list.size();
        unordered_map<string, int> m;
        for (int i = 1; i < n - 1; i += 2) {
            int val;
            varStark.push_back(m);
            if (list[i + 1][0] == '(')
                val = evaluate(list[i + 1]);
            else
                val = get_var(list[i + 1]);
            varStark.pop_back();
            m[list[i]] = val;
        }
        int val;
        varStark.push_back(m);
        if (list[n - 1][0] == '(') {
            val = evaluate(list[n - 1]);
        } else
            val = get_var(list[n - 1]);
        varStark.pop_back();
        return val;
    }
    int comp_var(string &str) {
        int val;
        if (str[0] == '(')
            val = evaluate(str);
        else
            val = get_var(str);
        return val;
    }
    int get_var(string &str) {
        for (int i = varStark.size() - 1; i >= 0; i--)
            if (varStark[i].count(str)) return varStark[i][str];
        return stoi(str);
    }
    int findEndIdx1(string &expression, int start) {
        int end = start, deep = 0;
        do {
            if (expression[end] == '(')
                deep++;
            else if (expression[end] == ')')
                deep--;
            end++;
        } while (deep > 0);
        return end;
    }
    int findEndIdx2(string &expression, int start) {
        int end = start;
        while (end < expression.size() && expression[end] != ' ') end++;
        return end;
    }
};