Expression Evaluation

Expression evaluation generally deals with the problem of inputting a string representing an expression and requiring the output of its value. There are also variations such as whether the expression contains parentheses, exponentiation, how many variables it contains, determining whether multiple expressions are equivalent, etc.

Expressions generally need to undergo syntax analysis (grammar parsing) before evaluation, or they can be analyzed and evaluated simultaneously. The role of syntax analysis is to check whether the input string is a valid expression, usually solved using a parser.

Expressions contain two types of characters: operands and operators. For an expression of length \(n\), with appropriate analysis methods, analysis and evaluation can be completed within \(O(n)\) time complexity.

Expression Tree and Reverse Polish Notation

One recursive method to analyze expressions is to treat the expression as a regular grammar rule, analyze it, split it into an expression tree as shown in the figure, and then perform operations bottom-up on the tree structure.

Performing tree traversal on the expression tree yields different types of expressions. Arithmetic expressions are divided into three types: prefix expressions, infix expressions, and suffix expressions. Infix expressions are the most commonly used in daily life; suffix expressions are easily understood by computers.

Preorder traversal corresponds to prefix expressions (Polish notation)
Inorder traversal corresponds to infix expressions
Postorder traversal corresponds to suffix expressions (Reverse Polish notation)

Reverse Polish notation (suffix expression) is a form of writing mathematical expressions where operators are placed after their operands. For example, the following expression:

\[ a+b*c*d+(e-f)*(g*h+i) \]

can be written in Reverse Polish notation as:

\[ abc*d*+ef-gh*i+*+ \]

Therefore, Reverse Polish notation corresponds one-to-one with expression trees. Reverse Polish notation does not require parentheses to indicate the order of operations; its operation order is uniquely determined.

The convenience of Reverse Polish notation lies in its ease of computation in linear time. For example: in the Reverse Polish expression \(3~2~*~1~-\), first compute \(3 \times 2 = 6\) (using the last operator, i.e., the top of the stack), then compute \(6 - 1 = 5\). It can be seen that for a Reverse Polish expression, one only needs to maintain a number stack, and each time an operator is encountered, take the two top elements of the stack, compute the result, and push it back onto the stack. Finally, the only element in the stack is the result of the Reverse Polish expression. This algorithm has \(O(n)\) time complexity.

Whether the recursive method of analyzing expressions is successful depends on whether the design of the grammar rules is reasonable, i.e., whether the specified expression tree can be successfully obtained. For example:

\[ a+b*c \]

Depending on the different precedence of the plus and multiplication operators, this infix expression may be transformed into two different expression trees. It can be seen that the design of grammar rules highly depends on operator precedence. Designing corresponding recursive grammar rules based on operator precedence is actually not an easy task.

The method introduced below treats the operator and its precedence as a whole, using a non-recursive method to directly analyze and compute expressions based on operator precedence.

Parenthesized Expressions Containing Only Left-Associative Binary Operators

Consider a simplified problem. Assume all operators are binary: all operators have two arguments. And all operators are left-associative: if operators have equal precedence, they are executed from left to right. Parentheses are allowed.

For the computation of infix expressions of this type, they can be converted to suffix expressions and then computed. Define two stacks to store operators and operands respectively. Whenever a number is encountered, it is directly placed into the operand stack. Each operator block corresponds to a pair of parentheses, and the operator stack is monotonic only within the operator block. Whenever an operator is encountered, the top elements of the operator stack within the operator block are examined, and appropriate pop operations are performed within the operator block to keep the operators in descending order of precedence. While popping, the corresponding sub-expression values are computed.

The following part uses "output" to mean outputting to the suffix expression, i.e., placing the number on the operand stack, or popping the operator and two operands, computing, and then pushing the result back onto the operand stack. Scan the infix expression from left to right:

If a number is encountered, output the number directly.
If a left parenthesis is encountered, place it on the operator stack.
If a right parenthesis is encountered, continuously output the top element of the stack until a left parenthesis is encountered, then pop the left parenthesis. In other words, execute all operators within a pair of parentheses.
If another operator is encountered, continuously output all operators with precedence greater than or equal to the current operator. Finally, push the new operator onto the operator stack.
After processing the entire string, some operators may still be in the stack, so output the remaining symbols in the stack in order, and the expression conversion ends.

Here is an implementation of this method for the four operators \(+\), \(-\), \(*\), \(/\):

Example Code

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 compute suffix expressions
  int r = st.top();                         // Take the top element, note the 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 modified to convert infix to suffix 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, place it on the operator stack
    } else if (s[i] == ')') {  // 3. If a right parenthesis is encountered, execute all operators within the pair of parentheses
      while (op.top() != '(') {
        process_op(st, op.top());
        op.pop();  // Continuously 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();  // Continuously output all operators with precedence >= 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();
}

The time complexity of this algorithm, which implicitly uses Reverse Polish notation to compute the value of an expression, is \(O(n)\). By slightly modifying the above implementation, one can also obtain the Reverse Polish expression in explicit form.

Unary Operators and Right-Associative Operators

Now assume the expression also contains unary operators, i.e., operators with only one argument. Unary plus and unary minus are common examples of unary operators.

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

Note that unary operators are generally preceded by another operator or an opening parenthesis; if the unary operator is at the very beginning of the expression, there is none. Before a binary operator, there is always an operand or a right parenthesis. Therefore, one can mark whether the next operator is unary.

Additionally, unary and binary operators need to be executed differently, with unary operators having 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, operators must be evaluated from right to left.

As mentioned, unary operators are usually right-associative. Another example of a right-associative operator is the exponentiation operator. For \(a \wedge b \wedge c\), it is usually considered as \(a^{b^c}\), not \((a^b)^c\).

To correctly handle such operators, the corresponding change is to delay the popping of operators if their precedence is equal.

The code that needs to be changed 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))))

where left_assoc is a function that determines whether the operator is left-associative.

Here is an implementation for the binary operators \(+\), \(-\), \(*\), \(/\) and the unary operators \(+\) and \(-\):

Example Code

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 {  // Take the top element, note the 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, place it on the operator stack
      may_be_unary = true;
    } else if (s[i] == ')') {  // 3. If a right parenthesis is encountered, execute all operators within the pair of parentheses
      while (op.top() != '(') {
        process_op(st, op.top());
        op.pop();  // Continuously 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();  // Continuously output all operators with precedence >= 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's license is Public Domain + Leave a Link; the English version's license is CC-BY-SA 4.0.

Exercises

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用