Question

Stacks are used by compilers to help in the process of evaluating expressions and generating machine-language code. In this and the next exercise, we investigate how compilers evaluate arithmetic expressions consisting only of constants, operators and parentheses. Humans generally write expressions like \(3+4\) and \(7 / 9\) in which the operator \((+\text { or } / \text { here })\) is written between its operands- -this is called infix notation. Computers "prefer" postfix notation, in which the operator is written to the right of its two operands. The preceding infix expressions would appear in postfix notation as \(34+\) and \(79 /\), respectively. To evaluate a complex infix expression, a compiler would first convert the expression to postfix notation and evaluate the postfix version. Each of these algorithms requires only a single left-toright pass of the expression. Each algorithm uses a stack object in support of its operation, but each uses the stack for a different purpose. In this exercise, you will write a Java version of the infix-to-postfix conversion algorithm. In the next exercise, you will write a Java version of the postfix expression evaluation algorithm. In a later exercise, you will discover that code you write in this exercise can help you implement a complete working compiler. Write class InfixToPostfixConverter to convert an ordinary infix arithmetic expression (assume a valid expression is entered) with single-digit integers such as $$(6+2) * 5-8 / 4$$ to a postfix expression. The postfix version of the preceding infix expression is (note that no parentheses are needed $$62+5 * 84 /-$$ The program should read the expression into StringBuffer infix and use one of the stack classes implemented in this chapter to help create the postfix expression in StringBuffer postfix. The algorithm for creating a postfix expression is as follows: a) Push a left parenthesis '(' on the stack. b) Append a right parenthesis ')' to the end of infix. c) While the stack is not empty, read infix from left to right and do the following: If the current character in infix is a digit, append it to postfix. If the current character in infix is a left parenthesis, push it onto the stack. If the current character in infix is an operator: Pop operators (if there are any) at the top of the stack while they have equal or higher precedence than the current operator, and append the popped operators to postfix. Push the current character in infix onto the stack. If the current character in infix is a right parenthesis: Pop operators from the top of the stack and append them to postfix until a left parenthesis is at the top of the stack. Pop (and discard) the left parenthesis from the stack. The following arithmetic operations are allowed in an expression: \+ addition \- subtraction * multiplication / division ^ exponentiation % remainder The stack should be maintained with stack nodes that each contain an instance variable and a reference to the next stack node. Some of the methods you may want to provide are as follows: a) Method convertToPostfix, which converts the infix expression to postfix notation. b) Method isOperator, which determines whether c is an operator. c) Method precedence, which determines whether the precedence of operator1 (from the infix expression) is less than, equal to or greater than the precedence of operator2 (from the stack). The method returns true if operator1 has lower precedence than operator2. Otherwise, false is returned. d) Method stackTop (this should be added to the stack class), which returns the top value of the stack without popping the stack.

Short answer

Convert infix by processing operands directly into postfix, handle operators using stack precedence, and process subexpressions with parentheses.

Step-by-step solution

Initialize and Prepare Input

Start by pushing a left parenthesis '(' onto the stack to serve as a marker. Append a right parenthesis ')' at the end of the infix expression to ensure that everything on the stack is popped and processed correctly.

Process Each Character of Infix

Loop through each character of the infix expression from left to right.

Handle Digits

If the current character in the infix expression is a digit, append it directly to the postfix StringBuffer, as digits are operands and don't need processing.

Handle Left Parentheses

If the current character is a left parenthesis '(', push it onto the stack to denote the beginning of a subexpression.

Handle Operators

If the current character is an operator, pop operators from the stack and append them to postfix as long as they have the same or higher precedence compared to the current operator. Then, push the current operator onto the stack.

Handle Right Parentheses

If the current character is a right parenthesis ')', pop operators from the stack and append them to the postfix expression until a left parenthesis '(' is at the top of the stack. Pop and discard the left parenthesis '('.

Finalize Postfix Expression

Continue the process until the stack is empty, ensuring that any remaining operators are appended to the postfix expression.

Key concepts

Infix to Postfix Conversion

Infix notation is familiar to us all. We use it daily; examples include expressions like \(3 + 4\) or \(6 \times (2 + 3)\). It places the operator between operands. However, this format is not ideal for computers. To simplify machine processing, expressions are often converted to postfix notation, where the operator follows its operands. For example, \(3 + 4\) becomes \(34+\). Postfix, also known as Reverse Polish Notation (RPN), simplifies expression evaluation as it eliminates the need for parentheses to denote operation precedence and associativity.
To perform this conversion, an algorithm reads the infix expression from left to right, using a stack to keep track of operators and parentheses, pushing and popping them as needed to form the final postfix expression. This method handles operator precedence neatly, ensuring the expression is evaluated in the correct order. By placing operators after their operands, postfix notation, or RPN, allows for straightforward processing by a stack without resorting to order of operations or parentheses nesting.

Stack Implementation

Stacks are instrumental in converting infix expressions to postfix and also in evaluating postfix expressions. A stack operates on the Last In, First Out (LIFO) principle, which means the last element added to the stack will be the first one to be removed. This makes the stack a perfect data structure for processing expressions where the most recent operator or parenthesis needs to be resolved first.
When implementing a stack for infix to postfix conversion, you will use operations like "push" to place an item (like an operator or parenthesis) onto the stack, and "pop" to remove the item on the top of the stack. Another useful method is "peek" or "stackTop," which lets you view the top item without removing it, crucial for checking precedence rules without altering the stack's state. You need a robust mechanism to maintain the stack’s integrity, ensuring efficient and error-free conversions.

Expression Evaluation

Once you have converted an infix expression to postfix, evaluating it becomes straightforward. In postfix notation, expressions are read from left to right, and the evaluation mechanism requires minimal additional processing.
For evaluation, utilize another stack to hold operands and intermediate results. As each character in the postfix expression is processed:

• If the character is a digit, push it onto the stack.
• If it's an operator, pop the requisite number of operands from the stack, apply the operator, and push the result back onto the stack.

This process continues until you've evaluated the entire expression. If you followed the steps correctly, the final result of the expression is the only item remaining on the stack. This algorithm’s efficiency and simplicity lie in it systematically handling each operator as soon as its operands are available.

Postfix Notation

Postfix notation or Reverse Polish Notation (RPN) is a mathematical notation where every operator follows all of its operands. This order eliminates the need for parentheses to specify evaluation order. For example, where an infix expression might look like \((A + B) \times C\), the equivalent postfix notation is \(AB+C+\).
Postfix notation aligns closely with stack-based processing, which provides a straightforward implementation for evaluators. It requires no hierarchical order joints or syntax rules beyond sequential reading, making it ideal for programming language compilation and computer calculations.
By converting infix expressions to postfix notation, we exploit a system that respects arithmetic standards while allowing consistent processing. Postfix notation optimizes expressions for evaluation algorithms, which effectively enhances execution speed in computing environments. The history of postfix lies deep within the development of computer science, reinforcing its foundational role in how compilers and calculators process mathematical expressions efficiently.