Algorithms for Parsing Arithmetic Expressions Algorithms for Parsing Arithmetic Expressions

Parsing a Postfix Expression (like 2 3 * 4 2 / + 5 3 * 6 + -)

The algorithm is:

Parsing an Infix Expression with No Parentheses (like 2 * 3 - 48/4 -4 * 5)

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

Parsing an Infix Expression with Parentheses (like ((2*4-6/3)*(3*5+8/4))-(2+3))

One stack is required. The algorithm is:

Code for Calculating with the Postfix Algorithm

#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 TEX by TTH, version 2.25.
On 12 Nov 2002, 14:05.