Parse Boolean Expression

XXX. Parse Boolean Expression

Stack

String

Expression Evaluation

Problem Statement:

Parse a boolean expression string and evaluate it. The expression can contain operators '!', '&', '|' and values 't', 'f'.

• ! is NOT operation (one argument)
• & is AND operation (multiple arguments)
• | is OR operation (multiple arguments)
• Expression is always valid and contains no spaces

Algorithm:

1. **Stack Approach**:
   • Push characters until closing parenthesis
   • Collect values between parentheses
   • Evaluate subexpression with operator
   • Push result back to stack

Implementation:

Java Solution:

class Solution {
    public boolean parseBoolExpr(String expression) {
        Stack st = new Stack<>();
        
        // Process each character in expression
        for (char c : expression.toCharArray()) {
            if (c == ')') {
                // Collect values inside parentheses
                ArrayList values = new ArrayList<>();
                while (st.peek() != '(') 
                    values.add(st.pop());
                
                st.pop();                            // Remove '('
                char op = st.pop();                  // Get operator
                
                // Evaluate and push result
                char result = evaluateSubExpr(op, values);
                st.push(result);
            } 
            else if (c != ',') {                    // Skip commas
                st.push(c);
            }
        }
        
        return st.peek() == 't';                    // Final result
    }
    
    private char evaluateSubExpr(char op, ArrayList values) {
        // NOT operation
        if (op == '!') 
            return values.get(0) == 't' ? 'f' : 't';
        
        // AND operation
        if (op == '&') {
            for (char val : values)
                if (val == 'f') return 'f';
            return 't';
        }
        
        // OR operation
        if (op == '|') {
            for (char val : values)
                if (val == 't') return 't';
            return 'f';
        }
        
        return 'f';                                  // Should never reach here
    }
}
                

Python Solution:

class Solution:
    def parseBoolExpr(self, expression: str) -> bool:
        stack = []
        
        def evaluate_subexpr(op: str, values: List[str]) -> str:
            if op == '!':
                return 't' if values[0] == 'f' else 'f'
            
            if op == '&':
                return 'f' if 'f' in values else 't'
            
            if op == '|':
                return 't' if 't' in values else 'f'
            
            return 'f'  # Should never reach here
        
        for c in expression:
            if c == ')':
                values = []
                # Collect values inside parentheses
                while stack[-1] != '(':
                    values.append(stack.pop())
                
                stack.pop()      # Remove '('
                op = stack.pop() # Get operator
                
                # Evaluate and push result
                result = evaluate_subexpr(op, values)
                stack.append(result)
            elif c != ',':       # Skip commas
                stack.append(c)
        
        return stack[-1] == 't'  # Final result
                

C++ Solution:

class Solution {
private:
    char evaluateSubExpr(char op, vector& values) {
        // NOT operation
        if (op == '!') 
            return values[0] == 't' ? 'f' : 't';
        
        // AND operation
        if (op == '&') {
            for (char val : values)
                if (val == 'f') return 'f';
            return 't';
        }
        
        // OR operation
        if (op == '|') {
            for (char val : values)
                if (val == 't') return 't';
            return 'f';
        }
        
        return 'f';  // Should never reach here
    }
    
public:
    bool parseBoolExpr(string expression) {
        stack st;
        
        for (char c : expression) {
            if (c == ')') {
                // Collect values inside parentheses
                vector values;
                while (st.top() != '(') {
                    values.push_back(st.top());
                    st.pop();
                }
                
                st.pop();        // Remove '('
                char op = st.top();
                st.pop();        // Remove operator
                
                // Evaluate and push result
                char result = evaluateSubExpr(op, values);
                st.push(result);
            }
            else if (c != ',')   // Skip commas
                st.push(c);
        }
        
        return st.top() == 't';  // Final result
    }
};
                

Explanation:

• **Expression Processing**:
  • Stack stores operators and operands
  • Process until closing parenthesis
  • Evaluate subexpression when parenthesis closes
• **Evaluation Rules**:
  • NOT (!): Invert single value
  • AND (&): False if any false, else true
  • OR (|): True if any true, else false
• **Implementation Notes**:
  • Skip commas during processing
  • Stack maintains expression structure
  • Results propagate upward through stack