Here is another one for you:
Reverse Polish Calculator
Implement the following stack functions.
empty() //returns true if stack is empty and false otherwise
push(argument) //pushes item argument on the stack
pop() //removes (but does not return) element on top of stack
top() //returns (but does not remove) element on top of stack
One very common use of a stack is found in calculators such as the Hewlett Packard calculators. Calculators that use a stack use reverse polish (or prefix) notation for arithmetic expressions. Reverse polish notation allows expressions to be entered without the use of parentheses. We are used to working with expressions in infix notation where a binary operator is placed between left and right operands. Parentheses are used to specify the order of operations. An infix expression is of the form LBR (left op, binary operator, right op) which corresponds to the postfix expression LRB (left op, right op, binary operator). Consider the following
Infix expression Postfix Expression
(a+b) ab+
(x - y - z) xy-z-
(x-y-z)/(u+v) xy-z-uv+/
(a^2 + b^2)*(m-n) a2^b2^+mn-*
Use ^ for exponentiation
To evaluate a postfix expression, P, you scan from left to right. When you encounter an operand, X, while scanning P, push it on to the evaluation stack, S. When you encounter an operator, B, you pop the topmost operand on the stack into a variable which represents the left operand, L. Finally, perform the operation B on L and R getting expression LBR, and push the result back on to the evaluation stack, S.
Make sure your postfix expression can handle:
- signed numbers
- multiple digit numbers
- floating point numbers
Delimit the items in the string with a blank space. The evaluation will be in two stages.
stage 1: Remove any excess blank spaces and any invalid characters from the string.
stage 2: Evaluate the postfix expression and display the answer.
Example:
Enter a postfix expression: -3.5 (2) * 12.75 +
Converted string: -3.5 2 * 12.75 +
Result: 5.75
