Sentiment (Expression Evaluation)

Solution Approach

Recursive Descent Parser

We implement a recursive descent parser that directly mirrors the grammar:

expr     -> and_expr ('|' and_expr)*
  and_expr -> not_expr ('&' not_expr)*
  not_expr -> '!' not_expr | atom
  atom     -> variable | '(' expr ')'

Each grammar rule becomes a function that consumes input characters and returns the boolean value of the corresponding sub-expression. The precedence is naturally encoded: parseExpr handles OR (lowest precedence), parseAnd handles AND, and parseNot handles NOT (highest precedence).

C++ Solution

#include <cstdio>
#include <cstring>
using namespace std;

char expr_str[10005];
int pos, len;
int vars[26]; // variable values for 'a'-'z'

int parseExpr();
int parseAnd();
int parseNot();
int parseAtom();

// expr -> and_expr ('|' and_expr)*
int parseExpr() {
    int val = parseAnd();
    while (pos < len && expr_str[pos] == '|') {
        pos++;
        val = val | parseAnd();
    }
    return val;
}

// and_expr -> not_expr ('&' not_expr)*
int parseAnd() {
    int val = parseNot();
    while (pos < len && expr_str[pos] == '&') {
        pos++;
        val = val & parseNot();
    }
    return val;
}

// not_expr -> '!' not_expr | atom
int parseNot() {
    if (pos < len && expr_str[pos] == '!') {
        pos++;
        return !parseNot();
    }
    return parseAtom();
}

// atom -> variable | '(' expr ')'
int parseAtom() {
    if (expr_str[pos] == '(') {
        pos++; // skip '('
        int val = parseExpr();
        pos++; // skip ')'
        return val;
    }
    int idx = expr_str[pos] - 'a';
    pos++;
    return vars[idx];
}

void stripSpaces(char* s) {
    int j = 0;
    for (int i = 0; s[i]; i++)
        if (s[i] != ' ')
            s[j++] = s[i];
    s[j] = '\0';
}

int main() {
    fgets(expr_str, sizeof(expr_str), stdin);
    // Remove trailing newline
    len = strlen(expr_str);
    if (len > 0 && expr_str[len-1] == '\n')
        expr_str[--len] = '\0';
    stripSpaces(expr_str);
    len = strlen(expr_str);

    // Read variable assignments
    int numVars;
    scanf("%d", &numVars);
    for (int i = 0; i < numVars; i++) {
        char c;
        int v;
        scanf(" %c %d", &c, &v);
        vars[c - 'a'] = v;
    }

    pos = 0;
    printf("%d\n", parseExpr());

    return 0;
}

Correctness

The parser processes each character exactly once, advancing the global position pos monotonically. The grammar is unambiguous (left-to-right evaluation within each precedence level), so the parser correctly evaluates the expression.

Each grammar production handles exactly the operators at its precedence level and delegates higher-precedence constructs to the next function.

Complexity Analysis

• Time complexity: $O(n)$ where $n$ is the expression length. Each character is visited at most once.

• Space complexity: $O(n)$ for the recursion stack (worst case: deeply nested parentheses or chained NOT operators). $O(1)$ additional space for the variable table.