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

March 23, 2012 admin 4 Comments

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 evaluate a postfix expression? Click here.

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/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
				
						// 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/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
				
						// ============================================================================
//    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/

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.

Want to evaluate a postfix expression? Click here for sample code.

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*/*

Was this article helpful?

👍 YesNo

Posted in: Advanced, C++, C++, Snippets Tags: array, c++, for loop, if/else, infix, postfix, template, While Loop

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

Cody says:

October 18, 2013 at 6:39 pm

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.

Reply
- admin says:
  
  October 19, 2013 at 12:31 am
  
  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
  
  Reply
Bogdan says:

June 3, 2018 at 8:45 am

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

Reply
- admin says:
  
  June 3, 2018 at 2:15 pm
  
  Hi, thanks for visiting!
  
  It appears there was a formatting issue in the code, it has since been updated.
  
  Thanks for catching that
  
  Reply

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

Related

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

Leave a ReplyCancel reply

Search

Compile Your Code Now

Translate Page

Popular Pages

Recent

Archives

Categories