The algorithm is:

- For each item in the postfix expression from the left:
- if the item is a number push it on the stack
- if the item is an operator (+,-,*, or /) then
- pop two numbers off the stack
- make a calculation: the second number
popped-operator-first number
- push the result on the stack

- pop two numbers off the stack

- if the item is a number push it on the stack
- When the loop is done the answer is the only item remaining
on the stack.

Two stacks are required, one for numbers and the other for operators. The algorithm is:

- For each item in the infix expression (no parens) from the right to the left
- If the item is a number then push it on the number stack.
- If the item is an operator (+,-,*, or /) and: the operator stack is empty or the operator on the top of the stack is higher in priority
(* and / are higher in priority than + or -), then
- Pop an operator from the operator stack.
- Pop two numbers off the number stack.
- Calculate using second number-operator-first number.
- Push the result on the number stack.
- Push the item on the operator stack.

- Else push the item on the operator stack.

- If the item is a number then push it on the number stack.
- After the loop, while the operator stack is not empty
- Pop an operator from the operator stack.
- Pop two numbers off the number stack.
- Calculate using second number-operator-first number.
- Push the result on the number stack.

- The answer is the last item in the number stack.

One stack is required. The algorithm is:

- Have a string available to store items
- For each item in the infix (with parens) expression
- If the item is a number then add it to the string with a space
- if the item is an operator then
- While the stack is not empty and an operator is at the top and the operator at the top is higher priority that the item then
= Pop the operator on the top of the stack

= Add the popped operator to the string with a space

- Push the item on the stack

- While the stack is not empty and an operator is at the top and the operator at the top is higher priority that the item then
- else if the item is a left paren
- Push the item on the stack

- else if the item is a right paren
- Pop a thing off of the stack.
- while that thing is not a left paren
= Add the thing to the string with a space

= Pop a thing off of the stack

- Pop a thing off of the stack.

- If the item is a number then add it to the string with a space
- While the stack is not empty
- Pop a thing off the stack.
- Add it to the string with a space.

- Pop a thing off the stack.
- Remove the last character (a space) from the string.

#include <iostream> #include <string> #include "Stack.h" int main () { string theExpress = "234*+45*67*+2/-"; cout << postfixCalculate (theExpress) << endl; return 0; } int postfixCalculate (string& theExpress) { //Restrictions: // * theExpress must be a postfix expression // * the numbers must be single digit and positive // * no spaces between items Stack theStack; //An int stack int first, second; //For each item in the postfix expression from the left: for (int n = 0; n < theExpress.size (); n++) { switch (theExpress [n]) { //if the item is an operator (+,-,*, or /) then // pop two numbers off the stack // make a calculation: the second number // popped-operator-first number // push the result on the stack case '*': getTwoOffStack (theStack, first, second); theStack.push (first * second); break; case '/': getTwoOffStack (theStack, first, second); theStack.push (first / second); break; case '+': getTwoOffStack (theStack, first, second); theStack.push (first + second); break; case '-': getTwoOffStack (theStack, first, second); theStack.push (first - second); break; // if the item is a number push it on the stack default: //str is a one character Cstring to hold the one digit number. //atoi is a library function that changes the Cstring to an int. //This won't work if str is an STL string. char str [3]; str [0] = theExpress [n]; str [1] = '\0'; theStack.push (atoi (str)); } } //When the loop is done, the answer is the only value left on the stack. int returnVal = theStack.getTop (); theStack.pop (); return returnVal; } void getTwoOffStack (Stack& theStack, int& first, int& second) { //This function takes (and removes) the top two numbers on the stack. //The topmost number is stored in first, the next one down in second. second = theStack.getTop (); theStack.pop (); first = theStack.getTop (); theStack.pop (); }

File translated from T

On 12 Nov 2002, 14:05.