Home > Articles, Compilers & Interpreters > Implementation of algorithm for converting an expression from infix to postfix notation.

Implementation of algorithm for converting an expression from infix to postfix notation.

The following program converts an expression from infix to postfix notation. The conversion is carried out with the help of a stack. For example, to turn the expression (A + B) into the postfix form A B +, we ignore the left parenthesis, convert the A to postfix form, we store the + operator on the stack, we convert B to postfix form and then, when find the right parenthesis, we pop the + operator from the top of the stack. In particular, the following implementation works only for the addition and multiplication of integers.

A full implementation of Shunting Yard 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<char> ops (N);

  for (int i = 0; i < N; i++) {
    if (a[i] == ')')
      cout << ops.pop () << " ";

    if ((a[i] == '+') || (a[i] == '*'))
      ops.push (a[i]);

    if ((a[i] >= '0') && (a[i] <= '9'))
      cout << a[i] << " ";
  }

  cout << 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: