A common use for stacks is in arithmetic expression evaluation. Our familiar infix expressions often require the use of parentheses to clarify order of evaluation. Not so with prefix and postfix notations. Section 3.8 in the text provides a discussion of how to evaluate postfix expressions. The algorithms below differ from the text, but provide a way to develop a solution without the implementation issues get in the way. Part 1 Data and notations Infix: a + b * c d (a + b) * c d a + b * c f / d a + b * (c f) / d 2 3 + 5 * 2 * 3 + 4 Postfix: a b c * + d a b + c * d a b c * + f d / a b c f - * d / + 2 3 5 2 * 4 * + 4 + Part 2 Thinking about what must be done Algorithm: postfix evaluation expr input postfix expression string token first token of expr while (token is not empty) do if (token is an operator) then topval pop stack nextval pop stack result apply token on topval and nextval push result on stack else value token string converted to integer push value on stack end if token next token of expr end while result pop stack Algorithm: infix to postfix conversion expr input infix expression string token first token of expr while (token is not empty) do if (token is ) then output token if (token is ) then push token on stack else if (token is an operator) then if (top of stack is () or stack is empty) then push token on stack else if (token has higher priority than stack top) then push token on stack else pop stack and write popped value to output push token on stack end if else if (token is a closing parenthesis) then pop operators and write to output until a ( is encountered pop ( but dont write it to output end if token next token of expr end while pop all operators and write to output Part 3 Implementation We will implement the postfix evaluation first. Details to be provided. Design and development Implementation