1. (Carrano) Programming Problems 6. page 221 Chap 6.

a. Exercises 12. Pag 219 Chap 6. Build an execution table to

each case (d), (f) and (h) similar to Fig. 6-5 p. 208

6. Consider simple infi x expressions that consist of single-digit operands; the operators +, -, *, and /; and parentheses. Assume that unary operators are illegal and that the expression contains no embedded spaces. Design and implement a class of infi x calculators. Use the algorithms given in this chapter to evaluate infi x expressions as entered into the calculator. You must fi rst convert the infi x expression to postfi x form and then evaluate the resulting postfi x expression.

a. Exercise 12. Convert the following infi x expressions to postfi x form by using the algorithm given in this chapter. Show the status of the stack after each step of the algorithm. a. a - b + c b. a - (b / c * d) c. a / (b * c) d. a / b / c - (d + e) * f e. (a + b) * c f. a * (b / c / d) + e g. a - (b + c ) h. a - (b + c * d) / e

FIGURE 6-5 A trace of the algorithm that converts the infi x expression a - ( b + c * d ) / e to postfi x form ch aStack (bottom to top) postfixExp a - ( b + c * d ) / e - - ( - ( - ( + - ( + - ( + * - ( + * - ( + - ( - - / - / a a a ab ab abc abc abcd abcd* abcd*+ abcd*+ abcd*+ abcd*+e abcd*+e/- Move operators from stack to postfixExp until "( " Copy operators from stack to postfixExp.

b. Implement the Pseudocode on p. 209. Use as an argument of

input a character string into your algorithm Use the expression

from Fig. 6-5 to demonstrate the operation of your c.

for ( each character ch in the infix expression) { switch (ch) { case operand: // Append operand to end of postfix expressionstep 1 postfixExp = postfixExp ch break case '(': // Save '(' on stackstep 2 aStack.push(ch) break case operator: // Process stack operators of greater precedencestep 3 while (!aStack.isEmpty() and aStack.peek() is not a '(' and precedence(ch) <= precedence(aStack.peek())) { Append aStack.peek() to the end of postfixExp aStack.pop() } aStack.push(ch) // Save the operator break case ')': // Pop stack until matching '(' step 4 while (aStack.peek() is not a '(') { Append aStack.peek() to the end of postfixExp aStack.pop() } aStack.pop() // Remove the open parenthesis break } } // Append to postfixExp the operators remaining in the stackstep 5 while (!aStack.isEmpty()) { Append aStack.peek() to the end of postfixExp aStack.pop() }

FIGURE 6-5 A trace of the algorithm that converts the infi x expression a - ( b + c * d ) / e to postfi x form ch aStack (bottom to top) postfixExp a - ( b + c * d ) / e - - ( - ( - ( + - ( + - ( + * - ( + * - ( + - ( - - / - / a a a ab ab abc abc abcd abcd* abcd*+ abcd*+ abcd*+ abcd*+e abcd*+e/- Move operators from stack to postfixExp until "( " Copy operators from stack to postfixExp.

C++ Main program

@file ArrayStack.h */

#include // for assert

#include "ArrayStack.h"//Header file

Template

ArrayStack::ArrayStack() : top(-1)

{

} //end default constructor

// Copy constructor and destructor are supplied by the compiler

template

bool ArrayStack::isEmpty() const

{

Return top < 0;

}//end is empty

template

bool ArrayStack::push(const ItemType& newEntry)

{

Bool result = false;

If( top

{

top++;

items[top] = newEntry;

result = true;

}//end push

template

bool ArrayStack::pop()

{

bool result = false;

If (!isEmpty())

{

top--;

result =true;

}// end if

return result;

}//end pop

template

ItemType arrayStack::peek() const

{

assert (! isEmpty()); //Enforce precondition

//stack is not empty: return top

return items[top];

} //end peek

//end of implementation file