<- People Behind Informatics


All 0-9 A B C D E F G H I J K L M N O P Q R S T U V W XY Z




 
Expression Evaluation
Compilers often translate infix expressions into postfix form, a notation in which the operators appear after their operands. The advantage of the postfix notation is that it eliminates the parenthesis of the infix notation without violating the original semantics. As an example let’s take the following infix expression: 2 * ((5 + 4) – 6) * 3). The proper order to evaluate this expression is (as every school child knows): 1.) 5 + 4 = 9 2.) 9 – 6 = 3 3.) 3 * 3 = 9 4.) 2 * 9 =18 In postfix notation the same expression looks like: 2 5 4 + 6 – 3 * * The operators always relate to the previous two operands – which may be of course intermediate results of previous operations. This can be ideally evaluated by a stack. The operators can be applied on the two top elements of the stack and the result is pushed back. This leads to the very same execution order and semantics. The above example could be executed as push(2), push(5), push(4), push(pop + pop), push(6), push(–pop + pop), push(3), push(pop * pop), push(pop * pop). The result is on the top of the stack, a print(pop) operation would display 18 and empty the stack. [Sources: Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman; Compilers – Principles, Techniques, and Tools; Laszlo Böszörmenyi: Notes to the Virtual Exhibition "People behind Informatics"]
 

 

<- People Behind Informatics


Home  |  Top  |  Search  |  Gallery  | Glossary  | Sitemap  |  Making Of  |  Help