4.6: Evaluation and Translation of Expressions

To illustrate the use of stacks, let us consider the problem of evaluating arithmetic expressions. People are accustomed to writing arithmetic expressions in infix notation, where an operator appears between its operands. Consequently, programming languages generally use infix notation to be "user friendly." Thus the programmer can write

(((a + (b/c * d)) + (a/w)) * b)/(((a * c) + d) + a)

Table 4.1 Notations for Two

Arithmetic Expressions

          a + (b * c)   (a + b) * c

Prefix    + a * bc      * + abc

Infix     a + b * c     a + b * c

Postfix   abc * +       ab + c *

Even humans must scan such an expression carefully, more than once, before discovering that its basis syntactic structure is (operand 1)/(operand 2). A serious problem for the compiler writers was how to translate such expressions without making many scans back and forth through them. The problem was compounded further because programmers were not required to write fully parenthesized expressions; this created the additional dilemma of how to resolve ambiguity. As will be shown below, ambiguity may be resolved by using a notation other than infix.

Consider the arithmetic expressions of Table 4.1. These arithmetic expressions are written in prefix, infix, and postfix notation. Prefix means that the operator appears to the left, before its operands, and postfix means that the operator appears to the right, after its operands. Although infix notation is what programmers normally use, there are contexts where prefix (or postfix) notation is used. For instance we write sqrt (x), f(x,y), and minimum (x,y)

Note that the prefix and postfix expressions of the first column are equivalent ways to express the infix expression a + (b * c), while the prefix and postfix expressions of the second column are equivalent to (a + b) * c. Unfortunately, the infix expressions of both columns are identical. This means that, unless parentheses are used, there is no way to distinguish between a + (b * c) and (a + b) * c using infix notation. Yet we can choose the proper prefix or postfix notation to make clear which of the two is intended, even though no parentheses (or special conventions) are used. This holds true in general for arithmetic expressions. For this reason, prefix and postfix notations are called parentheses-free notations. Compilers can easily process prefix and postfix expressions. Since postfix expressions are generally used, they are the main focus of the discussion that follows.

4.6.1 Postfix Expressions

4.6.2 Infix Expressions

4.6.3 Translating Infix to Postfix