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

• 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.

• 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

  • 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

• While the stack is not empty

  • Pop a thing off the stack.

  • Add it to the string with a space.

• 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 ();
}