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 operandsthis 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 of the expression. Each of these algorithms requires only a single left-to-right pass of the expression. Each algorithm uses a stack object in support of its operation, and in each algorithm the stack is used for a different purpose. In this exercise, you will write a \(\mathrm{C}++\) version of the infix-to- postfix conversion algorithm. In the next exercise, you will write a \(\mathrm{C}++\) version of the postfix expression evaluation algorithm. Later in the chapter, you will discover that code you write in this exercise can help you implement a complete working compiler. Write a program that converts 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 \(62+5 * 84 /\) The program should read the expression into character array infix and use modified versions of the stack functions implemented in this chapter to help create the postfix expression in character array postfix. The algorithm for creating a postfix expression is as follows: 1\. Push a left parenthesis ' (' onto the stack. 2\. Append a right parenthesis ' ' ' to the end of infix. \([\text { Page } 1039]\) 3\. 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, copy it to the next element of post \(f\) ix. 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 insert the popped operators in 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 insert them in 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 ' modulus [Note: We assume left to right associativity for all operators for the purpose of this exercise.] The stack should be maintained with stack nodes, each containing a data member and a pointer to the next stack node. Some of the functional capabilities you may want to provide are: a. function convertToPostfix that converts the infix expression to postfix notation b. function isoperator that determines whether \(c\) is an operator c. function precedence that determines whether the precedence of operator1 is less than, equal to or greater than the precedence of operator2 (the function returns1, 0 and \(1,\) respectively d. function push that pushes a value onto the stack e. function pop that pops a value off the stack f. function stackTop that returns the top value of the stack without popping the stack g. function isEmpty that determines if the stack is empty h. function printstack that prints the stack

Short answer

Convert infix expression using a stack-based approach, moving operators according to precedence to form a postfix expression.

Step-by-step solution

Convert Infix to Postfix Algorithm Initialization

Begin by initializing the stack to hold operators and parentheses. Push a left parenthesis '(' onto the stack. Append a right parenthesis ')' to the end of the infix expression to ensure proper alignment for processing.

Begin Infix Traversal

Start reading the infix expression from left to right. This process will continue until the stack is empty, indicating the whole expression has been processed.

Process Current Character as Operand (Digit)

If the current character in the infix expression is a digit (operand), directly copy it to the postfix expression. This is because operands will remain in the order they appear.

Handle Left Parenthesis

If the current character is a '(', push it into the stack. Parentheses have higher precedence and need to be processed within their own scope.

Process Operators

If the current character is an operator, check the stack for operators with greater or equal precedence. Pop such operators and add them to the postfix expression, then push the current operator onto the stack.

Handle Right Parenthesis

When a ')' is encountered, pop operators from the stack to the postfix expression until a '(' is encountered. Discard the '(' after it is popped from the stack.

Evaluate Stack Emptiness

Continue checking that the stack has been emptied after the traversal through the infix expression. Pop any remaining operators to the postfix expression, ensuring none are left lingering in the stack.

Key concepts

Stack Implementation

Stacks are fundamental data structures in C++ used for managing a list of elements with a Last In, First Out (LIFO) approach. This means the last element added to the stack is the first one to be removed. Imagine a stack of plates; you can only take the top plate off one at a time and add a new one on top.

Key operations include:

• Push: Adds an element to the top of the stack.
• Pop: Removes the top element of the stack.
• Peek/Top: Returns the top element without removing it.
• isEmpty: Checks if the stack is empty.

In the context of our expression conversion and evaluation, stacks help manage operators and parentheses efficiently. When translating an infix expression to postfix or evaluating an expression, stacks allow us to store operators temporarily and manage the order of operations correctly.

This ensures that the expression is processed in the right order even though the string of numbers and operators is read linearly.

Infix to Postfix Conversion

Converting infix expressions (like "3 + 4") to postfix notation ("34+") simplifies computations for computers. Postfix notation, also known as Reverse Polish Notation (RPN), doesn't require parentheses to express precedence, making evaluation straightforward. For conversion using a stack:

1. **Initialize**: Start by inserting a left parenthesis at the beginning and a right parenthesis at the end of the expression.

2. **Read from Left to Right**: Traverse the expression from beginning to end.

• If a digit is encountered, add it to the postfix expression directly.
• If a left parenthesis is found, push it onto the stack.
• If an operator appears, pop operators from the stack with higher or equal precedence and append them to the postfix expression. Then, push the current operator onto the stack.
• If a right parenthesis is reached, pop operators from the stack to the postfix expression until a left parenthesis is at the stack's top (then discard it).

This method guarantees that operators are output in the correct order of precedence, adhering strictly to the rules of arithmetic.

Expression Evaluation

Evaluating a postfix expression is far simpler than its infix counterpart. The process follows a straightforward utilization of stacks to achieve efficient computation.

Steps to evaluate a postfix expression involve:

• **Scan the Postfix Expression**: Read it from left to right.
• **Operand Handling**: When an operand (number) is encountered, push it onto the stack.
• **Operator Handling**: Upon encountering an operator, pop the required number of operands from the stack. Perform the operation and push the result back onto the stack.

For instance, in the postfix "62+5*84/", you would:

• Push 6, 2 to the stack, add them (yielding 8), and push the result.
• Push 5, then multiply with 8, resulting in 40.
• Push 8, 4, and perform division yielding 2.

Ultimately, the stack will hold the final result of the entire expression upon completion of the read, showcasing the merit of postfix for evaluation simplicity.

Operator Precedence

Operator precedence dictates the order in which operations are performed in expressions. In general, operations of higher precedence are performed before those of lower precedence.

Here is a simplified priority list from highest to lowest:

• **Parentheses ():** Operations within parentheses take the highest priority.
• **Exponentiation:** Has higher priority than multiplication and division.
• **Multiplication (*) and Division (/):** Equal precedence, evaluated from left to right.
• **Addition (+) and Subtraction (-):** Equal precedence, evaluated from left to right.

When converting infix to postfix, precedence ensures operators are moved to the correct positions relative to their operands, avoiding the need for parentheses in postfix expressions.

Similarly, during evaluation, precedence governs which operations to perform first, ensuring that the computational logic mirrors standard arithmetic rules. Understanding and applying precedence is crucial for writing efficient algorithms that manipulate complex expressions accurately.