Home > Articles, Compilers & Interpreters > Implementation of algorithm for calculating a postfix expression.

Implementation of algorithm for calculating a postfix expression.

The following program reads any postfix expression that includes integer multiplication and addition, evaluates the expression and displays the final result on the screen. The program stores the intermediate results in a stack of integers.

The terms (operands) are pushed onto the stack. The operators are applied to the two entries at the top of the stack (the two entries are popped from the stack); the result is pushed back into the stack. Because the order in which the two pop() functions are performed in the expression of this code is not specified in C++, the code for some non-commutative operators, such as the ones for subtraction and division, would be somewhat more complicated.

The program makes the implicit assumption that each integer or operator is followed by a delimiter – a specific character (say, empty space) – but the validity of the input data is not considered at all. The last ‘if’ and the loop ‘while’ perform a calculation similar to the function ‘atoi’ in C++. Every time we meet a new digit, we multiply the accumulated result by 10 and add the digit.

A more complete implementation of this algorithm can be found in the following project:

Valuation Calculator of Infix Mathematical Expressions

You should know that the implementation of the algorithm does not take into account issues of data input validation or proper management of dynamic memory (e.g. avoiding memory leaks) because it is only necessary to highlight the logic of the algorithm.

#include <iostream>

#include <cstdlib>
#include <cstring>

#include "STACK.h"

using namespace std;

int
main (int argc, char *argv[]) {
  if (!argv[1])
    return EXIT_FAILURE;

  char * a = argv[1];
  int N = strlen (a);

  STACK<int> save (N);

  for (int i = 0; i < N; i++) {
    if (a[i] == '+')
      save.push (save.pop () + save.pop ());

    if (a[i] == '*')
      save.push (save.pop () * save.pop ());

    if ((a[i] >= '0') && (a[i] <= '9'))
      save.push (0);

    while ((a[i] >= '0') && (a[i] <= '9'))
      save.push (10*save.pop () + (a[i++]-'0'));
  }

  cout << save.pop() << endl;

  return EXIT_SUCCESS;
}
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: