File Expressions.h

↰ Parent directory (ADS/stack)

Arithmetic expressions with a STACK [see File ADT.h], beyond the book: the operands are nonnegative integers, the operators the binary + - * / (the division truncated toward zero), and the tokens of an expression may be separated by spaces.

Definition (ADS/stack/Expressions.h)

Detailed Description

  • evalPostfix() evaluates an expression in postfix (reverse Polish) notation, e.g., 5 9 8 + 4 6 * * 7 + *: an operand is pushed, an operator pops its right operand t and then its left operand s and pushes s op t, and the value is the one item left, in O( n );

  • toPostfixParenthesized() turns a fully parenthesized infix expression, e.g., ( 5 * ( ( ( 9 + 8 ) * ( 4 * 6 ) ) + 7 ) ), into postfix: an operand goes to the output, an open parenthesis is skipped, an operator is pushed, and a closed parenthesis pops one operator to the output;

  • toPostfix() does the same for an infix expression with the usual precedences (* and / before + and -) and the associativity to the left, e.g., 35 + 17 * ( 40 - 9 ) - 7, by the shunting-yard algorithm of Dijkstra: an operator first pops to the output the operators on the stack, down to an open parenthesis, whose precedence is not lower than its own, and a closed parenthesis pops them down to the open one, which it removes.

The contracts [see File Contract.h]: each operator of a postfix expression finds two operands on the stack, one item is left at the end, no division is by 0 and no operation overflows a long (an operand beyond a long throws the std::out_of_range of std::stol); an infix expression has balanced parentheses and only the tokens above, and a fully parenthesized one has an operator for each pair of parentheses. The functions are defined in Expressions.tpp.

  1. Lukasiewicz, Elementy logiki matematycznej, Warszawa, 1929

    1. Dijkstra, Algol 60 translation, Report MR 34/61, Mathematisch Centrum, Amsterdam, 1961

  1. Sedgewick, Algorithms in C++, Parts 1-4, 3rd ed., Addison-Wesley, 1998, section 4.3

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Functions