Infix to Postfix in c++

 

Infix to Postfix Conversion in C++

Infix notation is a common way of writing mathematical expressions, where the operator is placed in between the operands. For example, the infix notation for the expression 2 + 3 is 2 + 3. On the other hand, postfix notation, also known as Reverse Polish notation, places the operator after the operands. In the case of the same expression, the postfix notation would be 2 3 +.

Converting infix notation to postfix notation is a common task in computer science, particularly in the field of compilers and interpreters. The process of converting infix notation to postfix notation involves using a stack to hold operators and operands. The algorithm for converting infix notation to postfix notation is relatively simple, but it can be tricky to implement in C++.

In this article, we will discuss the algorithm for converting infix notation to postfix notation and how to implement it in C++. We will also discuss some common pitfalls and how to avoid them.

The Algorithm

The algorithm for converting infix notation to postfix notation is relatively simple. The basic idea is to use a stack to hold operators and operands. The algorithm starts by scanning the infix expression from left to right. For each character in the expression, the algorithm does the following:

1. If the character is an operand, it is added to the output string.
2. If the character is an operator, it is pushed onto the stack.
3. If the character is a left parenthesis, it is pushed onto the stack.
4. If the character is a right parenthesis, operators are popped from the stack and added to the output string until a left parenthesis is encountered. The left parenthesis is then popped from the stack.

The algorithm continues to scan the expression until the end of the string is reached. At this point, any remaining operators on the stack are popped and added to the output string.

The following is a sample implementation of the algorithm in C++:

string infixToPostfix(string infix) {
 stack<char> operators;
 string postfix = "";
 for (int i = 0; i < infix.length(); i++)
 {
 char c = infix[i];
 if (isalnum(c))
 {
 postfix += c;
 } 
 else if (c == '(')
 {
 operators.push(c);
 }
 else if (c == ')')
 {
 while (operators.top() != '(')
 {
 postfix += operators.top();
 operators.pop();
 }
 operators.pop(); 
 } 
 else
  {
 while (!operators.empty() && operators.top() != '(') 
{
 postfix += operators.top();
 operators.pop(); 
 }
 operators.push(c); 
 } 
 }
 while (!operators.empty()) 
{
 postfix += operators.top(); 
 operators.pop();
 }
 return postfix;
 }

In this implementation, we use the STL stack class to hold operators and operands. The isalnum() function is used to check if a character is an operand or not. The left and right parenthesis are treated as special cases, as they are used to indicate the start and end of a sub-expression.