MCX2                                                                                                                 Math Department
Mr. Gary. Jaye                                                                                                    Danny Jaye, A.P.S.

2000 APCS  AB Exam Question 2  

An infix expression is an expression in which the operator is placed between the two operands, as in traditional algebraic notation. (For this problem, the only operations that we will consider are addition and multiplication.) Ambiguities in the expression are resolved by precedence rules (multiplication before addition) and left-to-right evaluation of operators of equal precedence. For example, in the following expression, the two multiplications would be evaluated first, then the additions would be evaluated from left to right.

3 * 4 + 5 * 2 + 8

A postfix expression is a sequence of numbers and arithmetic operators (+, *) that is evaluated from left to right by applying each operator to the two subexpressions immediately preceding it. For example, the following postfix expression is equivalent to the infix expression given above.

3 4 * 5 2 * + 8 +

In this postfix expression,

the first “ * “ applies to 3 and 4;                                                                                       3 * 4 = 12
the second “ * “ applies to 5 and 2;                                                                                  5 * 2 = 10
the first “ + “ applies to the results of these two subexpressions,                                     12 + 10 = 22
and the last first “ + “ applies to the last subexpression and the number 8,
      resulting in the final evaluation.                                                                                  22 + 8 = 30

Numbers and operators in the expression are called tokens. A token is either an integer or one of the operator + or *. Tokens are represented using the following definitions.

enum TokenType {PLUS, TIMES, NUMBER};
struct Token  {
   TokenType op; // op == NUMBER means token represents a value
   int value;     // the value represented if op is a NUMBER;
                  // otherwise, value is undefined
}

If a token has NUMBER for its op, then the token represents a value.

(a) Write overloaded operator<, as started below. If the precedence of the token lhs is less than the precedence of rhs, then operator< should return true. Tokens of type PLUS should have lower precedence than tokens of type TIMES, which should have lower precedence than tokens of type NUMBER.

Complete operator< below.

bool operator< (const Token & lhs, const Token & rhs) {

 (b) Write function InfixToPostfix, as started below. InfixToPostfix should fill the queue of tokens, postQ, with the postfix expression that is equivalent to the infix expression given in infixQ. The token at the front of infixQ represents the first token in the infix expression (3 in the example above), and the token at the back of the infixQ represents the last token in the expression (8 in the example above).

An infix expression can be translated to a postfix expression as follows. Use a stack to store operator tokens during processing. Process each token from the infix expression in turn.

• If a token is an operand (a number), then put it into the postfix expression.

• If a token is an operator and the stack is empty, then push the token on the stack. If the stack is not empty and the precedence of the token is less than or equal to the precedence of the token on top of the stack, then pop the token off the stack and put it into the postfix expression. Do this until the stack is empty or the precedence of the operator is greater than the precedence of the operator on top of the stack. Then push the current operator onto the stack.

• When the infix expression has been processed, put the operators remaining on the stack into the postfix expression.

In writing InfixToPostfix, you may call operator< specified in part (a). Assume that operator< works as specified, regardless of what you wrote in part (a).

Complete function InfixToPostfix below.

void InfixToPostfix(const apqueue<Token> & infixQ, apqueue<Token> & postQ) {
// precondition: the sequence of tokens in infixQ represents a valid infix expression
//                using +, *, and integers;  postQ is empty
//postcondition: the sequence of tokens in postQ represents a valid postfix expression
//                equivalent to the infix expression represented by infixQ

apqueue<Token> tempQ = infixQ;