Write a program that takes as input an infix expression and outputs the equivalent post-fix expression. The basic algorithm is con-
tained in "Translating Infix to Postfix Notation" on page 379. Assume that the input may contain numbers; variables; arithmetic operations +, -, *, and /; as well as parentheses. However, the expression need not be fully parenthesized, and when parentheses are missing, the usual C++ precedence rules are used to determine the order of evaluation. Your program should allow the user to enter additional ex-
pressions until the user says he or she wishes to end the program. For a more difficult assignment, enhance your program so that the expression need not be well formed; if it is not well formed, then the user is asked to reenter the expression.
Pseudocode (evaluating a post-script expression)
1. Initialize a stack of double numbers.
2. do
if (the next input is a number)
Read the next input and push it onto the stack.
else
{
Read the next character, which is an operation symbol.
Use top and pop to get the two numbers off the stack.
Combine these two numbers with the operation (using the second number
popped as the left operand), and push the result onto the stack.
}
while (there is more of the expression to read);
3. At this point, the stack contains one number, which is the value of the expression.
Pseudocode (Converting a Fully Parenthesized Infix Expression to a Postfix Expression)
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)
Read the operation symbol and push it onto the stack.
else
{
Read and discard the next input symbol (which should be a right parenthesis).
There should be an operation symbol on top of the stack, so write this symbol
to the output and pop it from the stack. (If there is no such symbol, then print an
error message indicating that there were too few operations in the infix expression,
and halt.) After popping the operation symbol, there should be a left parenthesis on
the top of the stack, so pop and discard this left parenthesis.
(If there was no left parenthesis, then the input did not have balanced
parentheses, so print an error message and halt.)
}
while (there is more of the expression to read);
Pseudocode(Converting an Infix Expression to a Postfix Expression (General Case))
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)
{
do
Print the top operation and pop it.
while none of these three conditions are true:
(1)The stack becomes empty, or
(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.
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).
Print the top operation and pop it; keep printing and popping 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
the left parenthesis.
}
while (there is more of the expression to read);