[736. LISP syntax parsing]

source ： Power button （LeetCode）

describe ：

Give you a similar Lisp String expression of statement expression, Calculate the result .

The expression syntax is as follows :

• Expressions can be integers ,let expression ,add expression ,mult expression , Or assigned variable . The result of an expression is always an integer .( Integers can be positive integers 、 Negtive integer 、0)

• let The expression uses "(let v1 e1 v2 e2 ... vn en expr)" In the form of , among let Always in string "let" To express , Next, one or more pairs of alternating variables and expressions will follow , in other words , The first variable v1 Is assigned as an expression e1 Value , The second variable v2 Is assigned as an expression e2 Value , By analogy ; Final let The value of the expression is expr Value of expression .

• add The expression is expressed as "(add e1 e2)" , among add Always in string "add" To express , This expression always contains two expressions e1、e2 , The end result is e1 The value of the expression and e2 The value of the expression and .

• mult The expression is expressed as "(mult e1 e2)" , among mult Always in string "mult" Express , This expression always contains two expressions e1、e2, The end result is e1 The value of the expression and e2 The value of the expression product .

• In this topic , Variable names start with lowercase characters , Follow after 0 One or more lowercase characters or numbers . For convenience ,"add" ,"let" ,"mult" Will be defined as “ keyword ” , Will not be used as a variable name .

• Last , Let's talk about the concept of scope . When calculating the expression corresponding to the variable name , In a computational context , First check the innermost scope （ In parentheses ）, Then check the external scopes in order . Every expression in the test case is legal . More details about scope , See example .

Example 1：

 Input ：expression = "(let x 2 (mult x (let x 3 y 4 (add x y))))"
 Output ：14
 explain ：
 Calculation expression  (add x y),  Checking variables  x  When the value of ,
 In the context of variables, the innermost scope checks outward in turn .
 First find  x = 3,  So here's  x  The value is  3 .

Example 2：

 Input ：expression = "(let x 3 x 2 x)"
 Output ：2
 explain ：let  The assignment operation in the statement can be processed in sequence .

Example 3：

 Input ：expression = "(let x 1 y 2 x (add x y) (add x y))"
 Output ：5
 explain ：
 first  (add x y)  The result is  3, And assign this value to  x . 
 the second  (add x y)  The result is  3 + 2 = 5 .

Tips ：

• 1 <= expression.length <= 2000
• exprssion There are no leading and trailing spaces in
• expressoin Different parts of （token） Separated by a single space
• The answer is consistent with all intermediate calculations 32-bit Integer range
• The expressions in the test cases are legal and the final result is an integer

Method 1 ： Recursive parsing

For an expression expression, If its first character is not equal to the left bracket ‘ ( ’ , Then it can only be an integer or variable ; Otherwise it is let, add and mult One of three expressions .

Defined function parseVar Used to parse variables and functions parseInt Used to parse integers . Use scope To record the scope , Each variable records all its values from outside to inside in turn , When searching, you only need to find the last value . We parse the expression recursively expression.

• expression The next character of is not equal to the left parenthesis ‘ ( ’

  • expression The next character of is a lowercase letter , Then the expression is a variable , Using functions parseVar Parse variables , And then in scope Find the last value of the variable, that is, the value of the innermost scope, and return the result .

  • expression The next character of is not a lowercase letter , Then the expression is an integer , Using functions parseInt Parse and return the result .

• Remove the left parenthesis , expression The next character in is ‘ l ’, So the expression is let expression . about let expression , You need to judge whether it has been resolved to the last expr expression .

  • If the next character is not lowercase , Or the next character after parsing the variable is the right parenthesis ‘ ) ’, The explanation is the last expr expression , Calculate its value and return the result . And we need to be in scope Middle clearance let The scope variable corresponding to the expression .
  • Otherwise, it means alternating variables vi And expressions ei , stay scope Put the variable vi Add an expression to the numeric list of ei The numerical .

• Remove the left parenthesis , expression The next character in is ‘ a ’, So the expression is add expression . Calculation add The two expressions corresponding to the expression e1 and e2 Value , Return one of the two and .

• Remove the left parenthesis ,expression The next character in is ‘ m ’, So the expression is mult expression . Calculation mult The two expressions corresponding to the expression e1 and e2 Value , Return one of the two product .

Code ：

class Solution {
    
private:
    unordered_map<string, vector<int>> scope;

public:
    int evaluate(string expression) {
    
        int start = 0;
        return innerEvaluate(expression, start);
    }

    int innerEvaluate(const string &expression, int &start) {
    
        if (expression[start] != '(') {
     //  Non expression , May be ： Integer or variable 
            if (islower(expression[start])) {
    
                string var = parseVar(expression, start); //  Variable 
                return scope[var].back();
            } else {
     //  Integers 
                return parseInt(expression, start);
            }
        }
        int ret;
        start++; //  Remove the left parenthesis 
        if (expression[start] == 'l') {
     // "let"  expression 
            start += 4; //  remove  "let "
            vector<string> vars;
            while (true) {
    
                if (!islower(expression[start])) {
    
                    ret = innerEvaluate(expression, start); // let  The last of the expression  expr  Value of expression 
                    break;
                }
                string var = parseVar(expression, start);
                if (expression[start] == ')') {
    
                    ret = scope[var].back(); // let  The last of the expression  expr  Value of expression 
                    break;
                }
                vars.push_back(var);
                start++; //  Remove spaces 
                int e = innerEvaluate(expression, start);
                scope[var].push_back(e);
                start++; //  Remove spaces 
            }
            for (auto var : vars) {
    
                scope[var].pop_back(); //  Clear variables in the current scope 
            }
        } else if (expression[start] == 'a') {
     // "add"  expression 
            start += 4; //  remove  "add "
            int e1 = innerEvaluate(expression, start);
            start++; //  Remove spaces 
            int e2 = innerEvaluate(expression, start);
            ret = e1 + e2;
        } else {
     // "mult"  expression 
            start += 5; //  remove  "mult "
            int e1 = innerEvaluate(expression, start);
            start++; //  Remove spaces 
            int e2 = innerEvaluate(expression, start);
            ret = e1 * e2;
        }
        start++; //  Remove the closing bracket 
        return ret;
    }

    int parseInt(const string &expression, int &start) {
     //  Analytic integer 
        int n = expression.size();
        int ret = 0, sign = 1;
        if (expression[start] == '-') {
    
            sign = -1;
            start++;
        }
        while (start < n && isdigit(expression[start])) {
    
            ret = ret * 10 + (expression[start] - '0');
            start++;
        }
        return sign * ret;
    }

    string parseVar(const string &expression, int &start) {
     //  Parse variables 
        int n = expression.size();
        string ret;
        while (start < n && expression[start] != ' ' && expression[start] != ')') {
    
            ret.push_back(expression[start]);
            start++;
        }
        return ret;
    }
};

Execution time ：0 ms, In all C++ Defeated in submission 100.00% Users of
Memory consumption ：8.5 MB, In all C++ Defeated in submission 75.73% Users of
Complexity analysis
Time complexity ： O(n), among n Is string expression The length of . Call function recursively innerEvaluate The time complexity of calling at a certain layer is O(k), among k For the pointer start The number of moves invoked at this layer . Throughout the recursive call , The pointer start Will traverse the entire string , So parse expression need O(n).
Spatial complexity ： O(n). preservation scope And the recursive call stack needs O(n) Space .

Method 2 ： State machine

Code ：

enum ExprStatus {
    
    VALUE = 0, //  The initial state 
    NONE,      //  Unknown expression type 
    LET,       // let  expression 
    LET1,      // let  The expression has been parsed  vi  Variable 
    LET2,      // let  The expression has parsed the last expression  expr
    ADD,       // add  expression 
    ADD1,      // add  The expression has been parsed  e1  expression 
    ADD2,      // add  The expression has been parsed  e2  expression 
    MULT,      // mult  expression 
    MULT1,     // mult  The expression has been parsed  e1  expression 
    MULT2,     // mult  The expression has been parsed  e2  expression 
    DONE       //  Parsing complete 
};

struct Expr {
    
    ExprStatus status;
    string var; // let  The variable of  vi
    int value; // VALUE  The number of States , perhaps  LET2  The value of the last expression of the state 
    int e1, e2; // add  or  mult  Two expressions of expression  e1  and  e2  The numerical 

    Expr(ExprStatus s) {
    
        status = s;
    }
};

class Solution {
    
private:
    unordered_map<string, vector<int>> scope;

public:
    int evaluate(string expression) {
    
        vector<vector<string>> vars;
        int start = 0, n = expression.size();
        stack<Expr> s;
        Expr cur(VALUE);
        while (start < n) {
    
            if (expression[start] == ' ') {
    
                start++; //  Remove space 
                continue;
            }
            if (expression[start] == '(') {
    
                start++; //  Remove the left parenthesis 
                s.push(cur);
                cur = Expr(NONE);
                continue;
            }
            string token;
            if (expression[start] == ')') {
     //  In essence, it turns the expression into a  token
                start++; //  Remove the closing bracket 
                if (cur.status == LET2) {
    
                    token = to_string(cur.value);
                    for (auto var : vars.back()) {
     //  Clear scope 
                        scope[var].pop_back();
                    }
                    vars.pop_back();
                } else if (cur.status == ADD2) {
    
                    token = to_string(cur.e1 + cur.e2);
                } else {
    
                    token = to_string(cur.e1 * cur.e2);
                }
                cur = s.top(); //  Get the upper level status 
                s.pop();
            } else {
    
                while (start < n && expression[start] != ' ' && expression[start] != ')') {
    
                    token.push_back(expression[start]);
                    start++;
                }
            }
            switch (cur.status) {
    
                case VALUE:
                    cur.value = stoi(token);
                    cur.status = DONE;
                    break;
                case NONE:
                    if (token == "let") {
    
                        cur.status = LET;
                        vars.emplace_back(); //  Record all variables in the scope of this layer ,  Convenient for subsequent removal 
                    } else if (token == "add") {
    
                        cur.status = ADD;
                    } else if (token == "mult") {
    
                        cur.status = MULT;
                    }
                    break;
                case LET:
                    if (expression[start] == ')') {
     // let  The last of the expression  expr  expression 
                        cur.value = calculateToken(token);
                        cur.status = LET2;
                    } else {
    
                        cur.var = token;
                        vars.back().push_back(token); //  Record all variables in the scope of this layer ,  Convenient for subsequent removal 
                        cur.status = LET1;
                    }
                    break;
                case LET1:
                    scope[cur.var].push_back(calculateToken(token));
                    cur.status = LET;
                    break;
                case ADD:
                    cur.e1 = calculateToken(token);
                    cur.status = ADD1;
                    break;
                case ADD1:
                    cur.e2 = calculateToken(token);
                    cur.status = ADD2;
                    break;
                case MULT:
                    cur.e1 = calculateToken(token);
                    cur.status = MULT1;
                    break;
                case MULT1:
                    cur.e2 = calculateToken(token);
                    cur.status = MULT2;
                    break;
            }
        }
        return cur.value;
    }

    int calculateToken(const string &token) {
    
        if (islower(token[0])) {
    
            return scope[token].back();
        } else {
    
            return stoi(token);
        }
    }
};

Execution time ：0 ms, In all C++ Defeated in submission 100.00% Users of
Memory consumption ：7.3 MB, In all C++ Defeated in submission 93.20% Users of
Complexity analysis
Time complexity ： O(n), among nn Is string expression The length of . State machine parsing will traverse the entire string , Therefore need O(n) Time for .
Spatial complexity ： O(n). The stack that saves the state and the scope variables all need O(n) Space .
author：LeetCode-Solution