The Postfix Polish Notation
To the main page

As a rule it's convenient to convert any arithmetical expression to the Postfix Polish Notation (PPN) in order to get rid of brackets contained in the expression. You can calculate expressions converted to PPN from left to right consistently.

There are two well known ways to convert an expression to PPN. Let's consider each of them:

1. The converting to PPN by means of the stack
We'll need a stack for variables which have char type because we get the origin expression as a string.

Let's consider each symbol consistently. There can be 4 possible situations:
1. The symbol is a number (or a variable). Then we just put it to our output string.
2. The symbol is a operation sign (such as: +, -, *, / ). Then we check the priority of the operation. The multiplication and the division have got the highest priority (3). The addition and the subtraction have got lower priority (2). An opening bracket has got the lowest priority (1).
When we've received one of these symbols we have to check the stack:
a) if the stack is empty or there are only symbols which priority is lower than the current symbol's priority there then we put the current symbol to the stack.
b) if the priority of the symbol disposed on the top of the stack is greater or equal to priority of the current symbol we take out symbols from the stack until this condition is broken; then we pass to the point a).
3. If the current symbol is an opening bracket we put it to the stack.
4. If the current symbol is a closing bracket we take out symbols from the stack until we find an opening bracket there (it must be a symbol with the priority 1); then we just destroy the opening bracket we've found. The closing bracket must be destroyed too.

If we've analysed all input string but there are still some symbols in the stack we have to take out and put them to the output string.

Let's consider one simple example:
The origin expression is
a + ( b - c ) * d
Let's consider each symbol:
Symbol
 Action
 The output string after this action
 The stack after this action
a
 'a' is a variable. We must put it to the output string
 a
 empty
+
 '+' is a sign of operation. We put it to the stack (stack is still empty so we needn't check the symbol's priority)
 a
 +
(
 '(' is an opening bracket. We put it to the stack. a
 + (
b
 'b' is a variable. We must put it to the output string a b
 + (
-
 '-' is a sign of operation. Its priority is 2. Now we must check the stack. There is '(' on the top of the stack. Its priority is 1. So we must put the current '-' symbol to the stack. a b
 + ( -
c
 'c' is a variable. We must put it to the output string a b c
 + ( -
)
 ')' is a closing bracket. We must take out symbols from the stack till we find an opening bracket. Then we destroy both brackets. a b c -
 +
*
 '-' is a sign of operation. Its priority is 3. We must check the stack: there is a '+' symbol on the top of the stack. Its priority is 2 and less than the priority of the '*' symbol. So we just put the current '*' symbol to the stack. a b c -
 + *
d
 'd' is a variable. We must put it to the output string a b c - d
 + *

Now we've parsed all the input string but there're still signs of operation in the stack. We must take them out and put them to the output string. Since the stack is a structure organized in according to the LIFO principle we take out the '*' symbol at first and then we take out the '+' symbol.
So we have got the final result:
a b c - d * +

Download the implementation of the algorithm.
This algorithm is also used in the Calc3 program disposed here (see the file named CPPNCalc.cpp).


2. The converting to PPN by means of the recursive descent
The implementation of this algorithm is several functions which call each other consistently.
The converting begins calling the begin() function which handles the addition and the subtraction (it stores signs of these operations in temporary variables and puts them to the output string when receives the management again).
The begin() function calls the mult_div() function handling the multiplication and the division (it stores signs of these operations in temporary variables and puts them to the output string when receives the management again)..
Then mult_div() function calls the symbol() function handling numbers (or variables) and brackets. If the symbol() function receives an opening bracket it calls the begin() function once more and then expects a closing bracket when receives the management again. If it doesn't receive a closing bracket there is some error in the expression.
If the symbol() function receives a variable it puts that variable to the output string.

The implementation in C++ (classes from the VCL were used for working with strings and exceptions): 

class TStr2PPN {
    AnsiString instr, outstr;     //input & output strings
    char curc;                    //the current character
    int iin;                      //the index of the input string

    char nextChar();              //get the next character
    void begin();                 //handle plus & minus
    void mult_div();              //handle multiplication & division
    void symbol();                //handle characters

  public:
    TStr2PPN() {                  //constructor
       iin = 1;
    }

    void convert(char *str);      //convert to PPN
    AnsiString get_outstr();      //get the output string
};

//get the next character
inline char TStr2PPN::nextChar() {
   if(iin <= instr.Length()) return curc = instr[iin++];
   return curc = '\0';
}

//get the output string
inline AnsiString TStr2PPN::get_outstr(){return outstr;}

//convert to PPN
void TStr2PPN::convert(char *str) {
   try {
      instr = str;
      outstr.SetLength(0);
      iin = 1;
      nextChar();
      //begin the convertation
      begin();
      if(iin != (instr.Length()+1) || curc != '\0') {
         throw Exception("Syntax error");
      }
      if(!isalpha(instr[instr.Length()]) && instr[instr.Length()]!=')') {
         throw Exception("Syntax error");
      }
   }
   catch(...) {throw;}
}

//handle plus & minus
void TStr2PPN::begin() {
   try {
       mult_div();
       while(curc=='+' || curc=='-') {
          char temp = curc;
          nextChar();
          mult_div();
          outstr += temp;
       }
   }
   catch(...) {throw;}
}

//handle multiplication & division
void TStr2PPN::mult_div() {
   try {
       symbol();
       while(curc=='*' || curc=='/') {
          char temp = curc;
          nextChar();
          symbol();
          outstr += temp;
       }
   }
   catch(...) {throw;}
}

//handle characters
void TStr2PPN::symbol() {
   try {
      if(curc=='(') {
         nextChar();
         begin();
         if(curc!=')') {
            throw Exception("Error: wrong number of brackets");
         }
         else nextChar();
      }
      else
         if(isalpha(curc)) {
            outstr += curc;
            nextChar();
         }
         else {throw Exception("Syntax error");}
   }
   catch(...) {throw;}
}

Download the implementation in C++


3. The algorithm of the calculation of the expression written in PPN
We'll use the stack for numbers (or for variables if there are some). The algorithm is very simple. Now our input string is the expression written in PPN:
1. If the current symbol is a number we put it to the stack.
2. If the current symbol is any operation sign we have to take out two numbers from the stack and use them as operands for that operation and then put the result to the stack.
When we've analysed all input string there must be one number in the stack. And this number is a result of our calculation.

Let's consider one simple example:
The origin expression is
7 5 2 - 4 * +

Let's consider each symbol:
Symbol
 Action
 The stack after this action
7
 '7' is a number. We put it to the stack.
 7
5
 '5' is a number. We put it to the stack. 7 5
2
 '2' is a number. We put it to the stack. 7 5 2
-
 '-' is a sign of operation. We have to take out two numbers (5 and 2) from the stack and implement the 5 - 2 = 3 operation. Then we put the result to the stack. 7 3
4
 '4' is a number. We put it to the stack. 7 3 4
*
 '*' is a sign of operation. We have to take out two numbers (3 and 4) from the stack and implement the 3 * 4 = 12 operation. Then we put the result to the stack. 7 12
+
 '+' is a sign of operation. We have to take out two numbers (7 and 12) from the stack and implement the 7 + 12 = 19 operation. Then we put the result to the stack. 19

Now we've parsed all the input string and there's one number in the stack. This number is a result of our calculation.

The implementation in C++: 

int calculate(string str_in) {
  Stack<int> val_stack;                //stack
  int n1, n2, res;
  
  for(i = 0; i<str_in.length(); ++i) {
    if(isNumber(str_out[i])) {   
       val_stack.push(str_out[i]);
    }
    else {
      n2 = val_stack.pop(); 
      n1 = val_stack.pop();
      switch(str_out[i]) {
         case '+': res = n1 + n2; break;
         case '-': res = n1 - n2; break;
         case '*': res = n1 * n2; break;
         case '/': res = n1 / n2; break;
         default: cout<<"Error !\n";
      }
      val_stack.push(res);
    }
  }
  return val_stack.pop();
}

This algorithm is also used in the Calc3 program disposed here (see the file named CPPNCalc.cpp).

To the main page

Rambler's Top100