Parsing A Boolean Expression

Leetcode Problem:

• Parsing A Boolean Expression

Summary

• Given a boolean expression, evaluate the expression and return the result.

Approach

• This solution uses a stack to parse the boolean expression
• It first pushes each character of the expression into the stack
• When it encounters a '(', it pops characters from the stack until it finds a ')'
• Then it processes the operator and the operands, and pushes the result back into the stack
• Finally, it returns the result at the top of the stack.

Complexity

• O(n), where n is the length of the expression
• This is because each character in the expression is pushed and popped from the stack once.

Explanation

• The parseBoolExpr function takes a string expression as input and returns a boolean value
• It uses a stack to parse the expression
• The stack is used to keep track of the operators and operands
• The function processes each operator and the operands, and pushes the result back into the stack
• Finally, it returns the result at the top of the stack.

Solution Code:

struct _stack{
    char arr[10001];
    int top;
    _stack(){
        top = 0;
    }
    void push(char a){
        arr[top++] = a;
    }
    char pop(){
        return arr[--top];
    }
    bool empty(){
        return top == 0;
    }
    char peek(){
        return arr[top - 1];
    }
};

class Solution {
public:
    _stack st;
    vector v;
    char strToInt[256];
    bool process(char oper, vector& v){
        if (oper == '!'){
            return !(strToInt[v[0]]);
        }
        if (oper == '|'){
            bool res = strToInt[v[0]];
            for(int i = 1; i < v.size(); i++){
                res |= strToInt[v[i]];
                if(res) return true;
            }
        }
        bool res = strToInt[v[0]];
        for(int i = 1; i < v.size(); i++){
            res &= strToInt[v[i]];
        }
        return res;
    }

    bool parseBoolExpr(string expression) {
        strToInt['f'] = 0;
        strToInt['t'] = 1;
        bool res;
        for(char c: expression){
            if (c != ')'){
                if(c == ',') continue;
                st.push(c);
                continue;
            } 
            while(st.peek() != '('){
                v.push_back(st.pop());
            }
            st.pop();
            char oper = st.pop();
            res = process(oper,v );
            st.push(res ? 't':'f');
            v.clear();
        }
        return st.peek() == 't' ? true: false;
    }
};