## C++ || Stack Based Infix To Postfix Conversion (Single Digit)

This page consists of another homework assignment which was presented in a C++ Data Structures course. No matter which institution you attend, it seems every instructor assigns a program similar to this at one time or another.

Want to convert & evaluate multi digit, decimal, and negative numbers? Click here!

REQUIRED KNOWLEDGE FOR THIS PROGRAM

```What Is Infix? What Is Postfix? Stack Data Structure Cin.getline How To Convert To Postfix The Order Of Operations #include "ClassStackType.h"```

The program demonstrated on this page has the ability to convert a normal infix equation to postfix equation, so for example, if the user enters the infix equation of (1*2)+3, the program will display the postfix result of 12*3+.

Before we get into things, here is a helpful algorithm for converting from infix to postfix in pseudo code:

``` // An algorithm for infix to postfix expression conversion. // For example, a + b - c translates to a b + c - // a + b * c translates to a b c * + // (1 + 2) / (5 + 6) goes to 1 2 + 5 6 + / // Valid operands are single digits: 0-9, a-z, A-Z // Valid operators are: +, -, *, /, (, ), ^, \$ // Highest precedence: ^, \$ // Lowest precedence: +,- // ) never goes on stack. // ( has lowest precedence on the stack and highest precedence outside of stack. // Bottom of the stack has the lowest precedence than any operator. // Use a prec() function to compare the precedence of the operators based on the above rules. // Note there is little error checking in the algorithm! void ConvertInfixToPostfix(string infix) { while there is input { if input is a number or a letter place onto postfix string else if input is '(' // '(' has lowest precedence in the stack, highest outside push input on stack else if input is ')' while stack is not empty and top of stack is not '(' place item from top of stack onto postfix string pop stack if stack is not empty // pops '(' off the stack pop stack else error // no matching '(' else if input is a math operator if stack is empty push input on stack else if prec(top of stack) >= prec(current math operator) while stack is not empty and prec(top of stack) >= prec(current math operator) place item from top of stack onto postfix string pop stack push current math operator on stack else error } while stack is not empty { place item from top of stack onto postfix string pop stack } }// http://programmingnotes.org/ 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647 // An algorithm for infix to postfix expression conversion.// For example,   a + b - c     translates to   a b + c -//                a + b * c     translates to   a b c * +//                (1 + 2) / (5 + 6)   goes to   1 2 + 5 6 + /// Valid operands are single digits: 0-9, a-z, A-Z// Valid operators are: +, -, *, /, (, ), ^, \$// Highest precedence:   ^, \$// Lowest precedence:    +,-// ) never goes on stack.// ( has lowest precedence on the stack and highest precedence outside of stack.// Bottom of the stack has the lowest precedence than any operator.// Use a prec() function to compare the precedence of the operators based on the above rules.// Note there is little error checking in the algorithm! void ConvertInfixToPostfix(string infix){  while there is input  {    if input is a number or a letter        place onto postfix string    else        if input is '('  // '(' has lowest precedence in the stack, highest outside            push input on stack        else if input is ')'            while stack is not empty and top of stack is not '('                place item from top of stack onto postfix string                pop stack            if stack is not empty // pops '(' off the stack                pop stack            else error  // no matching '('        else if input is a math operator            if stack is empty                push input on stack            else                if prec(top of stack) >= prec(current math operator)                    while stack is not empty and prec(top of stack) >= prec(current math operator)                        place item from top of stack onto postfix string                        pop stack                push current math operator on stack        else error  }  while stack is not empty  {    place item from top of stack onto postfix string    pop stack  }}// http://programmingnotes.org/ ```

======= INFIX TO POSTFIX CONVERSION =======

This program uses a custom template.h class. To obtain the code for that class, click here.

``` Infix To Postfix Conversion (Single Digit) C++ // ============================================================================ // Author: Kenneth Perkins // Date: Mar 23, 2012 // Taken From: http://programmingnotes.org/ // File: PostfixConversion.cpp // Description: Demonstrate the use of a stack based infix to // postfix conversion. // ============================================================================ #include <iostream> #include <cctype> #include <cstdlib> #include <cstring> #include "ClassStackType.h" using namespace std; // function prototypes void DisplayDirections(); void ConvertInfixToPostfix(char* infix); int OrderOfOperations(char token); bool IsMathOperator(char token); int main() { // declare variables char expression[50]; // array holding the infix data // display directions to user DisplayDirections(); // get data from user cout<<"\nPlease enter an infix expression: "; cin.getline(expression, sizeof(expression)); cout <<"\nThe Infix expression = "<<expression<<endl; ConvertInfixToPostfix(expression); cout<<"The Postfix expression = "<<expression<<endl; return 0; }// end of main void DisplayDirections() { cout << "\n==== Infix to Postfix Conversion ====\n" <<"\nMath Operators:\n" <<"+ || Addition\n" <<"- || Subtraction\n" <<"* || Multiplication\n" <<"/ || Division\n" <<"% || Modulus\n" <<"^ || Power\n" <<"\$ || Square Root\n" <<"Sample Infix Equation: (((4^5)*14)/(\$(23+2)-2))*(1%2)/(2*4)\n"; }// end of DisplayDirections void ConvertInfixToPostfix(char* infix) { // declare function variables int infixCounter = 0; int postfixCounter = 0; char token = 'a'; char postfix[50]; StackType<char> charStack; // loop thru array until there is no more data while(infix[infixCounter] != '\0') { // push numbers/letters onto 'postfix' array if(isdigit(infix[infixCounter]) || isalpha(infix[infixCounter])) { postfix[postfixCounter] = infix[infixCounter]; ++postfixCounter; } else if(isspace(infix[infixCounter])) { // DO NOTHING } else if(IsMathOperator(infix[infixCounter])) { // if stack is empty, place first math operator onto stack token = infix[infixCounter]; if(charStack.IsEmpty()) { charStack.Push(token); } else { // get the current math operator from the top of the stack token = charStack.Top(); charStack.Pop(); // use the 'OrderOfOperations' function to check equality // of the math operators while(OrderOfOperations(token) >= OrderOfOperations(infix[infixCounter])) { // if stack is empty, do nothing if(charStack.IsEmpty()) { break; } // place the popped math operator from above ^ // onto the postfix array else { postfix[postfixCounter] = token; ++postfixCounter; // pop the next operator from the stack and // continue the process until complete token = charStack.Top(); charStack.Pop(); } } // push any remainding math operators onto the stack charStack.Push(token); charStack.Push(infix[infixCounter]); } } // push outer parentheses onto stack else if(infix[infixCounter] == '(') { charStack.Push(infix[infixCounter]); } else if(infix[infixCounter] == ')') { // pop the current math operator from the stack token = charStack.Top(); charStack.Pop(); while(token != '(' && !charStack.IsEmpty()) { // place the math operator onto the postfix array postfix[postfixCounter] = token; ++postfixCounter; // pop the next operator from the stack and // continue the process until complete token = charStack.Top(); charStack.Pop(); } } else { cout<<"\nINVALID INPUT\n"; exit(1); } ++infixCounter; } // place any remaining math operators from the stack onto // the postfix array while(!charStack.IsEmpty()) { postfix[postfixCounter] = charStack.Top(); ++postfixCounter; charStack.Pop(); } postfix[postfixCounter] = '\0'; // copy the data from the postfix array into the infix array // the data in the infix array gets sent back to main // since the array is passed by reference strcpy(infix,postfix); }// end of ConvertInfixToPostfix int OrderOfOperations(char token) {// this function checks priority of each math operator int priority = 0; if(token == '^'|| token == '\$') { priority = 4; } else if(token == '*' || token == '/' || token == '%') { priority = 3; } else if(token == '-') { priority = 2; } else if(token == '+') { priority = 1; } return priority; }// end of OrderOfOperations bool IsMathOperator(char token) {// this function checks if operand is a math operator switch(token) { case '+': return true; break; case '-': return true; break; case '*': return true; break; case '/': return true; break; case '%': return true; break; case '^': return true; break; case '\$': return true; break; default: return false; break; } }// http://programmingnotes.org/ 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216 // ============================================================================//    Author: Kenneth Perkins//    Date:   Mar 23, 2012//    Taken From: http://programmingnotes.org///    File:  PostfixConversion.cpp//    Description: Demonstrate the use of a stack based infix to //         postfix conversion.// ============================================================================#include <iostream>#include <cctype>#include <cstdlib>#include <cstring>#include "ClassStackType.h"using namespace std; // function prototypesvoid DisplayDirections();void ConvertInfixToPostfix(char* infix);int OrderOfOperations(char token);bool IsMathOperator(char token); int main(){    // declare variables    char expression[50]; // array holding the infix data        // display directions to user    DisplayDirections();        // get data from user    cout<<"\nPlease enter an infix expression: ";    cin.getline(expression, sizeof(expression));        cout <<"\nThe Infix expression = "<<expression<<endl;        ConvertInfixToPostfix(expression);        cout<<"The Postfix expression = "<<expression<<endl;        return 0;}// end of main void DisplayDirections(){    cout << "\n==== Infix to Postfix Conversion ====\n"        <<"\nMath Operators:\n"        <<"+ || Addition\n"        <<"- || Subtraction\n"        <<"* || Multiplication\n"        <<"/ || Division\n"        <<"% || Modulus\n"        <<"^ || Power\n"        <<"\$ || Square Root\n"        <<"Sample Infix Equation: (((4^5)*14)/(\$(23+2)-2))*(1%2)/(2*4)\n";}// end of DisplayDirections void ConvertInfixToPostfix(char* infix){    // declare function variables    int infixCounter = 0;    int postfixCounter = 0;    char token = 'a';    char postfix[50];    StackType<char> charStack;        // loop thru array until there is no more data    while(infix[infixCounter] != '\0')    {        // push numbers/letters onto 'postfix' array        if(isdigit(infix[infixCounter]) || isalpha(infix[infixCounter]))        {            postfix[postfixCounter] = infix[infixCounter];            ++postfixCounter;        }        else if(isspace(infix[infixCounter]))        {            // DO NOTHING        }        else if(IsMathOperator(infix[infixCounter]))        {            // if stack is empty, place first math operator onto stack            token = infix[infixCounter];            if(charStack.IsEmpty())            {                charStack.Push(token);            }            else            {                // get the current math operator from the top of the stack                token = charStack.Top();                charStack.Pop();                                 // use the 'OrderOfOperations' function to check equality                // of the math operators                while(OrderOfOperations(token) >= OrderOfOperations(infix[infixCounter]))                {                    // if stack is empty, do nothing                    if(charStack.IsEmpty())                    {                        break;                    }                    // place the popped math operator from above ^                    // onto the postfix array                    else                    {                        postfix[postfixCounter] = token;                        ++postfixCounter;                        // pop the next operator from the stack and                         // continue the process until complete                        token = charStack.Top();                        charStack.Pop();                    }                }                // push any remainding math operators onto the stack                charStack.Push(token);                charStack.Push(infix[infixCounter]);            }        }        // push outer parentheses onto stack        else if(infix[infixCounter] == '(')        {            charStack.Push(infix[infixCounter]);        }        else if(infix[infixCounter] == ')')        {            // pop the current math operator from the stack            token = charStack.Top();            charStack.Pop();            while(token != '(' && !charStack.IsEmpty())            {                // place the math operator onto the postfix array                postfix[postfixCounter] = token;                ++postfixCounter;                 // pop the next operator from the stack and                // continue the process until complete                token = charStack.Top();                charStack.Pop();            }        }        else        {            cout<<"\nINVALID INPUT\n";            exit(1);        }        ++infixCounter;    }        // place any remaining math operators from the stack onto    // the postfix array    while(!charStack.IsEmpty())    {        postfix[postfixCounter] = charStack.Top();        ++postfixCounter;         charStack.Pop();    }        postfix[postfixCounter] = '\0';    // copy the data from the postfix array into the infix array    // the data in the infix array gets sent back to main    // since the array is passed by reference    strcpy(infix,postfix);}// end of ConvertInfixToPostfix int OrderOfOperations(char token){// this function checks priority of each math operator    int priority = 0;        if(token == '^'|| token == '\$')    {        priority = 4;     }    else if(token == '*' || token == '/' || token == '%')    {        priority = 3;    }    else if(token == '-')    {        priority = 2;    }    else if(token == '+')    {        priority = 1;    }    return priority; }// end of OrderOfOperations bool IsMathOperator(char token){// this function checks if operand is a math operator     switch(token)     {        case '+':             return true;            break;        case '-':             return true;            break;        case '*':            return true;            break;        case '/':             return true;            break;        case '%':             return true;            break;        case '^':             return true;            break;         case '\$':             return true;            break;          default:            return false;            break;     }}// http://programmingnotes.org/ ```

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

Want to convert & evaluate multi digit, decimal, and negative numbers? Click here!

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output
(Note: the code was compile three separate times to display different output)

`====== RUN 1 ======`

``` ==== Infix to Postfix Conversion ==== Math Operators: + || Addition - || Subtraction * || Multiplication / || Division % || Modulus ^ || Power \$ || Square Root Sample Infix Equation: (((4^5)*14)/(\$(23+2)-2))*(1%2)/(2*4) Please enter an infix expression: ((a+b)+c)/(d^e) The Infix expression = ((a+b)+c)/(d^e) The Postfix expression = ab+c+de^/ ====== RUN 2 ====== ==== Infix to Postfix Conversion ==== Math Operators: + || Addition - || Subtraction * || Multiplication / || Division % || Modulus ^ || Power \$ || Square Root Sample Infix Equation: (((4^5)*14)/(\$(23+2)-2))*(1%2)/(2*4) Please enter an infix expression: (3*5)+(7^6) The Infix expression = (3*5)+(7^6) The Postfix expression = 35*76^+ ====== RUN 3 ====== ==== Infix to Postfix Conversion ==== Math Operators: + || Addition - || Subtraction * || Multiplication / || Division % || Modulus ^ || Power \$ || Square Root Sample Infix Equation: (((4^5)*14)/(\$(23+2)-2))*(1%2)/(2*4) ```

```Please enter an infix expression: (((4^5)*14)/(\$(23+2)-2))*(1%2)/(2*4) The Infix expression = (((4^5)*14)/(\$(23+2)-2))*(1%2)/(2*4) The Postfix expression = 45^14*232+\$2-/12%24*/*```

👍 YesNo

### 4 Responses to C++ || Stack Based Infix To Postfix Conversion (Single Digit)

1. Cody says:

The infix B/A-C exposes a flaw in your program. For many other expressions it is correct though.

At lines 90 and 91 you would have ‘/’ be the only item in the stack, and ‘-‘ be the next operand to compare the Operation Order with. token becomes ‘/’ and you pop it from the stack, but this makes the stack empty.

Hello

This program was implemented in such a way to mimic that of a simple calculator in that it requires you (the user) to enter in the correct parenthesis into the program to render the correct postfix conversions.

For example,

Entering the infix expression “B/A-C” renders the postfix conversion of BAC-/
Whereas entering the infix expression “(B/A)-C” renders the postfix conversion of BA/C-

Implementing this in such a way is not a flaw, but is the way this program was intended to operate.

Hope this helps

2. Bogdan says:

Hello, at while(infix[infixCounter] != ”) (line 67) and postfix[postfixCounter] = ”; (line 157) compiler gives me an error: empty character constant. what should i do?