Write a program that evaluates an arithmetic expression in infix notation, without full parentheses. Use the following algorithm: There are two stacks: a numbers stack and an operators stack. When a number appears, push it onto the numbers stack. Any parenthesis or operator should be treated as described in Step 2 of Figure 6.10 on page 351—with one change. Whenever you pop an operation off the stack, you should immediately use that operation by popping two numbers, applying the operation, and pushing the answer back on the numbers stack.

Transcribed Image Text:

FIGURE 6.10 Converting an Infix Expression to a Postfix Expression (General Case) Pseudocode 1. Initialize a stack of characters to hold the operation symbols and parentheses. 2. do if (the next input is a left parenthesis) Read the left parenthesis and push it onto the stack. else if (the next input is a number or other operand) Read the operand and write it to the output. else if (the next input is one of the operation symbols) { Pop and print operations off the stack until one of three things occurs: (1) The stack becomes empty, (2) the next symbol on the stack is a left parenthesis, or (3) the next symbol on the stack is an operation with lower precedence than the next input symbol. When one of these situations occurs, stop popping, read the next input symbol, and push this symbol onto the stack. } else { Read and discard the next input symbol (which should be a right parenthesis). Pop and print operations off the stack until the next symbol on the stack is a left parenthesis. (If no left parenthesis is encountered, then print an error message indicating unbalanced parentheses and halt.) Finally, pop and discard the left parenthesis. } while (there is more of the expression to read); 3. Pop and print any remaining operations on the stack. (There should be no remaining left parentheses; if there are, the input expression did not have balanced parentheses.)