Expression Evaluation

Expression evaluation generally means taking a string representing an expression as input and outputting its value. There are also variants, such as whether the expression contains parentheses, whether it uses exponentiation, how many variables it contains, and whether several expressions are equivalent.

Expressions generally need to be parsed before evaluation (grammar parsing), although parsing and evaluation can also be performed at the same time. Parsing checks whether the input string is a valid expression, and is generally handled by a parser.

An expression contains two kinds of characters: operands and operators. For an expression of length $n$, a suitable parsing method can complete parsing and evaluation in $O(n)$ time.

Expression Trees and Reverse Polish Notation

One recursive way to parse an expression is to treat it as an ordinary grammar, parse it, and decompose it into the expression tree shown in the figure, then perform the calculations bottom-up on the tree.

Performing tree traversal on an expression tree gives different types of expressions. Arithmetic expressions have three forms: prefix, infix, and postfix expressions. Infix expressions are the most common in everyday use, while postfix expressions are easier for computers to understand.

• Preorder traversal corresponds to a prefix expression (Polish notation).
• Inorder traversal corresponds to an infix expression.
• Postorder traversal corresponds to a postfix expression (Reverse Polish notation).

A Reverse Polish expression (postfix expression) is a way of writing a mathematical expression in which each operator appears after its operands. For example, the following expression:

can be written in Reverse Polish notation as:

Thus, a Reverse Polish expression and an expression tree correspond one-to-one. A Reverse Polish expression needs no parentheses, because its evaluation order is uniquely determined.

The convenience of Reverse Polish notation is that it can be evaluated easily in linear time. For example, in the Reverse Polish expression $3~2~*~1~-$, first compute $3 \times 2 = 6$ using the last operator, namely the operator at the top of the stack, and then compute $6 - 1 = 5$. As can be seen, for a Reverse Polish expression, it is enough to maintain a stack of numbers; whenever an operator is encountered, remove the two top elements, push the result of the operation back onto the stack. At the end, the only element in the stack is the value of the Reverse Polish expression. This algorithm has time complexity $O(n)$.

Whether recursive parsing succeeds depends on whether the grammar is designed appropriately, that is, whether it can successfully produce the specified expression tree. For example:

Because the plus and multiplication operators have different precedence, this infix expression can be converted into two different expression trees. This shows that grammar design depends heavily on operator precedence. Designing corresponding recursive grammar rules with operator precedence is in fact not easy.

The method introduced below treats operators and their precedence as a whole, and uses a non-recursive method to parse and evaluate an expression directly according to operator precedence.

Parenthesized Expressions with Only Left-Associative Binary Operators

Consider a simplified problem. Assume that all operators are binary, meaning that every operator has two operands. Also assume that all operators are left-associative: when operators have equal precedence, they are executed from left to right. Parentheses are allowed.

To evaluate an infix expression of this type, we can convert it to a postfix expression and then evaluate it. Define two stacks to store operators and operands separately; whenever a number is encountered, put it directly on the operand stack. Each operator block corresponds to a pair of parentheses, and the operator stack is monotonic only within an operator block. Whenever an operator is encountered, find the elements in the topmost operator block on the operator stack and, within that block, pop operators as appropriate so that their precedences remain in descending order; evaluate the corresponding subexpression at the same time.

In the following, “output” means outputting to the postfix expression: either putting the number on the operand stack, or popping an operator and two operands, performing the operation, and pushing the result back onto the operand stack. Scan the infix expression from left to right:

1. If a number is encountered, output the number directly.
2. If a left parenthesis is encountered, put it on the operator stack.
3. If a right parenthesis is encountered, repeatedly output the top element of the stack until a left parenthesis is encountered, then pop the left parenthesis. In other words, execute all operators inside the pair of parentheses.
4. If another operator is encountered, repeatedly output all operators whose precedence is greater than or equal to that of the current operator. Finally, push the new operator onto the operator stack.
5. After the entire string has been processed, some operators may remain on the stack, so output the remaining symbols in order and finish the conversion.

An implementation of this method for the four operators $+$, $-$, $*$, and $/$ appears below:

bool delim(char c) { return c == ' '; }

bool is_op(char c) { return c == '+' || c == '-' || c == '*' || c == '/'; }

int priority(char op) {
  if (op == '+' || op == '-') return 1;
  if (op == '*' || op == '/') return 2;
  return -1;
}

void process_op(stack<int>& st, char op) {  // can also be used to evaluate a postfix expression
  int r = st.top();                         // pop the top elements, paying attention to their order
  st.pop();
  int l = st.top();
  st.pop();
  switch (op) {
    case '+':
      st.push(l + r);
      break;
    case '-':
      st.push(l - r);
      break;
    case '*':
      st.push(l * r);
      break;
    case '/':
      st.push(l / r);
      break;
  }
}

int evaluate(string& s) {  // can also be adapted to convert an infix expression to a postfix expression
  stack<int> st;
  stack<char> op;
  for (int i = 0; i < (int)s.size(); i++) {
    if (delim(s[i])) continue;

    if (s[i] == '(') {
      op.push('(');  // 2. If a left parenthesis is encountered, put it on the operator stack
    } else if (s[i] == ')') {  // 3. If a right parenthesis is encountered, execute all operators inside the pair of parentheses
      while (op.top() != '(') {
        process_op(st, op.top());
        op.pop();  // repeatedly output the top element until a left parenthesis is encountered
      }
      op.pop();                // pop the left parenthesis
    } else if (is_op(s[i])) {  // 4. If another operator is encountered
      char cur_op = s[i];
      while (!op.empty() && priority(op.top()) >= priority(cur_op)) {
        process_op(st, op.top());
        op.pop();  // repeatedly output all operators whose precedence is at least that of the current operator
      }
      op.push(cur_op);  // push the new operator onto the operator stack
    } else {            // 1. If a number is encountered, output the number directly
      int number = 0;
      while (i < (int)s.size() && isalnum(s[i]))
        number = number * 10 + s[i++] - '0';
      --i;
      st.push(number);
    }
  }

  while (!op.empty()) {
    process_op(st, op.top());
    op.pop();
  }
  return st.top();
}

This algorithm implicitly uses a Reverse Polish expression to evaluate the expression and has time complexity $O(n)$. With a slight modification to the implementation above, the Reverse Polish expression can also be obtained explicitly.

Unary Operators and Right-Associative Operators

Now suppose that the expression also contains unary operators, that is, operators with only one operand. Unary plus and unary minus are common examples of unary operators.

One difference in this case is that we need to determine whether the current operator is unary or binary.

Notice that a unary operator is generally preceded by another operator or an opening parenthesis, or by nothing if it is at the very beginning of the expression. A binary operator is always preceded by an operand or a closing parenthesis. Therefore, we can mark whether the next operator is unary.

In addition, unary and binary operators need to be processed differently, with unary operators given higher precedence than all binary operators. Note that some unary operators, such as unary plus and unary minus, are actually right-associative.

Right-associative means that whenever precedence is equal, the operators must be evaluated from right to left.

As mentioned above, unary operators are usually right-associative. Another example of a right-associative operator is exponentiation. The expression $a \wedge b \wedge c$ is usually interpreted as $a^{b^c}$ rather than $(a^b)^c$.

To handle such operators correctly, the corresponding change is to defer popping an operator when the precedences are equal.

The code change is as follows. Change:

while (!op.empty() && priority(op.top()) >= priority(cur_op)) 

to:

while (!op.empty() &&
       ((left_assoc(cur_op) && priority(op.top()) >= priority(cur_op)) ||
        (!left_assoc(cur_op) && priority(op.top()) > priority(cur_op))))

Here, left_assoc is a function that determines whether an operator is left-associative.

Here is an implementation of the binary operators $+$, $-$, $*$, and $/$, together with the unary operators $+$ and $-$:

bool delim(char c) { return c == ' '; }

bool is_op(char c) { return c == '+' || c == '-' || c == '*' || c == '/'; }

bool is_unary(char c) { return c == '+' || c == '-'; }

int priority(char op) {
  if (op < 0)  // unary operator
    return 3;
  if (op == '+' || op == '-') return 1;
  if (op == '*' || op == '/') return 2;
  return -1;
}

void process_op(stack<int>& st, char op) {
  if (op < 0) {
    int l = st.top();
    st.pop();
    switch (-op) {
      case '+':
        st.push(l);
        break;
      case '-':
        st.push(-l);
        break;
    }
  } else {  // pop the top elements, paying attention to their order
    int r = st.top();
    st.pop();
    int l = st.top();
    st.pop();
    switch (op) {
      case '+':
        st.push(l + r);
        break;
      case '-':
        st.push(l - r);
        break;
      case '*':
        st.push(l * r);
        break;
      case '/':
        st.push(l / r);
        break;
    }
  }
}

int evaluate(string& s) {
  stack<int> st;
  stack<char> op;
  bool may_be_unary = true;
  for (int i = 0; i < (int)s.size(); i++) {
    if (delim(s[i])) continue;

    if (s[i] == '(') {
      op.push('(');  // 2. If a left parenthesis is encountered, put it on the operator stack
      may_be_unary = true;
    } else if (s[i] == ')') {  // 3. If a right parenthesis is encountered, execute all operators inside the pair of parentheses
      while (op.top() != '(') {
        process_op(st, op.top());
        op.pop();  // repeatedly output the top element until a left parenthesis is encountered
      }
      op.pop();  // pop the left parenthesis
      may_be_unary = false;
    } else if (is_op(s[i])) {  // 4. If another operator is encountered
      char cur_op = s[i];
      if (may_be_unary && is_unary(cur_op)) cur_op = -cur_op;
      while (!op.empty() &&
             ((cur_op >= 0 && priority(op.top()) >= priority(cur_op)) ||
              (cur_op < 0 && priority(op.top()) > priority(cur_op)))) {
        process_op(st, op.top());
        op.pop();  // repeatedly output all operators whose precedence is at least that of the current operator
      }
      op.push(cur_op);  // push the new operator onto the operator stack
      may_be_unary = true;
    } else {  // 1. If a number is encountered, output the number directly
      int number = 0;
      while (i < (int)s.size() && isalnum(s[i]))
        number = number * 10 + s[i++] - '0';
      --i;
      st.push(number);
      may_be_unary = false;
    }
  }

  while (!op.empty()) {
    process_op(st, op.top());
    op.pop();
  }
  return st.top();
}

References

This page is mainly translated from the blog post Разбор выражений. Обратная польская нотация and its English translation Expression parsing. The Russian version is licensed under Public Domain + Leave a Link; the English version is licensed under CC-BY-SA 4.0.

Further Reading

1. Operator-precedence_parser
2. Shunting yard algorithm

Problems

1. NOIP2013 Junior Group: Expression Evaluation
2. Postfix Expression
3. Transform the Expression