Question

Write class PostfixEvaluator, which evaluates a postfix expression such as $$62+5=84 /-$$ The program should read a postfix expression consisting of digits and operators into a String- Buffer. Using modified versions of the stack methods implemented earlier in this chapter, the pro- gram should scan the expression and evaluate it (assume it is valid). The algorithm is as follows: a) Append a right parenthesis ')' to the end of the postfix expression. When the right- parenthesis character is encountered, no further processing is necessary. b) When the right-parenthesis character has not been encountered, read the expression from left to right. If the current character is a digit, do the following: Push its integer value on the stack (the integer value of a digit character is its value in the computer’s character set minus the value of '0' in Unicode). Otherwise, if the current character is an operator: Pop the two top elements of the stack into variables x and y. Calculate y operator x. Push the result of the calculation onto the stack. c) When the right parenthesis is encountered in the expression, pop the top value of the stack. This is the result of the postfix expression. [Note: In b) above (based on the sample expression at the beginning of this exercise), if the operator is '/', the top of the stack is 2 and the next element in the stack is 8, then pop 2 into x, pop 8 into y, evaluate 8/2 and push the result, 4, back on the stack. This note also applies to operator '-'.] The arithmetic operations allowed in an expression are: \+ addition \- subtraction * multiplication / division ^ exponentiation % remainder The stack should be maintained with one of the stack classes introduced in this chapter. You may want to provide the following methods: a) Method evaluatePostfixExpression, which evaluates the postfix expression. b) Method calculate, which evaluates the expression op1 operator op2. c) Method push, which pushes a value onto the stack. d) Method pop, which pops a value off the stack. e) Method isEmpty, which determines whether the stack is empty. f) Method printStack, which prints the stack.

Short answer

The result of the expression is obtained after processing all characters and is the sole item left on the stack.

Step-by-step solution

Append Right Parenthesis

Begin by appending a right parenthesis ')' to the end of the postfix expression. This serves as a marker that indicates when processing of the expression should stop.

Initialize Stack

Initialize an empty stack which will be used to store operands temporarily during the evaluation of the expression.

Process Characters in Expression

Read the postfix expression from left to right until encountering the appended right parenthesis. For each character, determine if it is a digit or an operator.

Handle Digit Characters

If a character is a digit, convert it to its integer value by subtracting the '0' Unicode value (i.e., cast the character to int and subtract 48), and then push this integer onto the stack.

Handle Operator Characters

If the character is an operator (+, -, *, /, etc.), pop the top two elements from the stack. Store the first popped element as x and the second as y, then perform the operation y operator x, and push the result back onto the stack.

Obtain Result

Once the right parenthesis is encountered, pop the top value off the stack. This value is the final result of the evaluated postfix expression.

Key concepts

Stack Implementation

In the evaluation of postfix expressions, a stack is crucial for temporarily storing operands as they are processed. The stack functions as a simple abstract data type (ADT) that follows the Last In, First Out (LIFO) principle. This means that the most recent item added to the stack will be the first one to be removed.
Common operations associated with stacks for postfix evaluation include:

• Push: Adding an element to the top of the stack.
• Pop: Removing the top element from the stack.
• Peek: Viewing the top element without removing it, although this is not mandatory for postfix evaluation.
• IsEmpty: Checking if the stack is empty.

These operations help manage the operands needed for arithmetic operations, ensuring that they are readily accessible in the correct order for computation as the expression is evaluated.

Arithmetic Operations

When evaluating a postfix expression, it's essential to understand the basic arithmetic operations: addition, subtraction, multiplication, division, exponentiation, and modulus. Each operator requires two operands that are popped from the stack and a result that is pushed back onto the stack.
Here's a breakdown of some key operations:

• Addition (+): Takes two operands \(a\) and \(b\), computes \(a + b\).
• Subtraction (-): Evaluates \(y - x\), where \(x\) is the first popped and \(y\) is the second.
• Multiplication (*): Multiplies two operands to get \(a \cdot b\).
• Division (/): Calculates \(y / x\), applying rules to handle division by zero.
• Exponentiation (^): Raises \(y\) to the power of \(x\).
• Modulus (%): Finds the remainder \((y \mod x)\).

These arithmetic operations form the heart of the evaluation process, transforming the abstract symbols of a postfix expression into a concrete numerical result.

Expression Parsing

Parsing involves reading and interpreting the postfix expression, character by character, to distinguish between operands and operators. This step-by-step examination determines the correct sequence of operations to perform.
In postfix notation, each operator follows all of its operands, removing the need for parentheses unlike infix notation. Begin parsing from the left, using the stack to handle operands as follows:

• Identify digits and convert them to integer values, pushing them onto the stack.
• Encounter an operator and pop the stack to retrieve operands as inputs to that operator.
• Proceed until the appended closing parenthesis signals the evaluation's end.

Effective parsing ensures correct order and application of arithmetic operations, aligning computational intent with the postfix notation.

Operator Precedence

Unlike infix expressions, where operator precedence (i.e., the order in which operations occur) is crucial, postfix expressions don't require awareness of precedence during parsing or evaluation. This is because the position of operators in postfix notation inherently dictates their execution order.
Still, understanding precedence is useful when converting infix expressions to postfix. In infix, precedence rules are:

• Parentheses: Evaluate operations within first.
• Exponents: Resolve next, following right to left.
• Multiplication/Division/Modulus: Equal precedence, handled left to right.
• Addition/Subtraction: Processed last, left to right.

When parsing a postfix expression, precedence has already been handled. The stack and postfix structure ensure each operator is applied in the proper sequence without requiring additional rules.