Computer Science Stuff

Break down of Infix to Postfix

Infix and Postfix notations are two different but equivalent ways of writing expressions. The easiest way to demonstrate the differences is by looking at examples of operators that take two operands.

Infix notation: X + Y
Infix notation is the most common way we express mathematical calculations to solve equations or expressions. For example when we input 5+6 into a calculator, our calculator catches the infix expression and breaks it down and returns the result of 11. Imagine it as a way of effectively communicating our problem so we can get the proper result.

Postfix notation: X Y +
Postfix notation is the translation of infix notation separated into fragments for calculation. With postfix notation we evaluate infix expression from left to right. With numbers we instantly input them in the final expression. With operators (+, -, *, /, %) we create an array or stack to input in operators and each operator (+, -, *, /, %) has a special rule.

Note about Operators :
If the scanned character is an Operand and the stack is not empty, compare the precedence of the character with the element on top of the stack (topStack). If topStack has higher precedence over the scanned character Pop the stack else Push the scanned character to stack. Repeat this step as long as stack is not empty and topStack has precedence over the character.

Priority:

Higher: *, /, %

Lower: +, -

Better explanantion

When putting in lower priority items into stack it pops out everything, but when putting in higher priority items if the top item is lower than it is placed into the stack it doesn’t pop it out. Anything that has equal priority is popped out.

Infix Expression :

Any expression in the standard form like “5*6-4/5″ is an Infix expression.

Clear Example

Evaluation of the expression:

Note: the operators would not bold (+, -, / ) also the right end of the stack at the top

Step 1:

original expression: 5*6-4/5

stack:

postfix expression: 5

Step 2:

original expression: 5*6-4/5

push *

stack: *

postfix expression: 5

Step 3:

original expression: 5*6-4/5

stack: *
postfix expression: 5 6

Step 4:

original expression: 5*6-4/5

pop * push -

stack: -
postfix expression: 5 6 *

Step 5:

original expression: 5*6-4/5

stack: -
postfix expression: 5 6 * 4

Step 6:

original expression: 5*6-4/5

push /

stack: – /
postfix expression: 5 6 * 4

Step 7:

original expression: 5*6-4/5

stack: – /
postfix expression: 5 6 * 4 5

Step 8:

original expression: 5*6-4/5

end of expression pop everything off

stack: – /

pop / pop -
postfix expression: 5 6 * 4 5 / -

Postfix Expression :

The Postfix form of the above expression is “56*45/-”.

CODE

To download this code click here infix to postfix

Here is a clear example of a C++ program below

// To include the libraries we are going to use in the program

#include // For using cin, cout and endl

#include // For using the string functions

#include // For using the functions to identifying types such digits (0,3,67) and letters (a,d,f,h,z)

using namespace std; // To access its functionality inside our header files

// Functions prototypes, these are declared ahead of time so we can use them after main and also so we know what

// functions are coming up ahead of time

bool error(string ); // to check expression for errors
void check(); // checks and changes the priority of a stack
void topostfix(string ); // to convert from infix to postfix
void push(string ); // to push character onto the stack
void pop(string ); // to pop character off the stack

//———————————————-
// intopost.cpp
//
// The purpose of this program is to translate
// infix to postfix
//
//
//———————————————

// Global variables, they can accessed from anywhere in the program

// This particular variable (priority) is what influences the events of the program as far as when to push and pop

// variables out the program

int priority=0;

string postfix, stack, stack1;

int main()
{
string expression;
// Enter in your expression

cout << “Enter in your expression to be converted from infix to postfix\nEnter in zero to end the loop\n”;
cin >> expression;

// This checks for errors or inappropriate characters placed into the program

if ( error(expression) ) { // check expression for errors
cout << “Program will not execute expression is incorrect\n”;
}
else {
topostfix(expression);
cout << “Here is your postfix expression ” << postfix << endl;
}

return 0;
} // end of main

void topostfix(string expression)
{
// postfix and priority is a global variable

string here, number, hold, again=expression;

cout << “\nSTART\n”;

for (int a=0; a < expression.length(); a++) {

number = here = expression[a];
cout << “The expression ” << here << endl;
cout << “The postfix ” << postfix << endl;

// The program detects a operator in the expression it executes the statements below

if ( expression[a] == ‘+’ || expression[a] == ‘-’) {
if (priority <= 2 ) {pop(here); push(here);}
else push(here);
}
else if ( expression[a] == ‘*’ || expression[a] == ‘/’ || expression[a] == ‘%’ ) {
if (priority == 1 ) {here=stack[0]; stack[0]=expression[a]; postfix = postfix + here; }
else push(here);
}
else if ( expression[a] == ‘(’ ) push(here);
else if ( expression[a] == ‘)’ ) pop(here);

else if ( isdigit(again[a]) ) { // for dealing with multiple digits and single digit numbers
if ( isdigit(again[a+1]) ) {
int b=a+1;
while ( isdigit(again[b]) ) {
hold=again[b];
number = number + hold; // number already equals the string here
++b;
}
postfix = postfix + ‘ ‘ + number;
a=b-1;
}
else {
postfix = postfix + ‘ ‘ + number;
}

} // end of else if
cout << “\nPOSTFIX “<< postfix << endl;
} // end of for

postfix = postfix + ‘ ‘ + stack;
}

// Check to see what operator was inputted in the expression and sets the priority t

void check ()
{
cout << “This is the first element ” << stack[0] << endl;
switch (stack[0]) {
case ‘*’:
case ‘/’:
case ‘%’:
priority=1; break;
case ‘+’:
case ‘-’:
priority=2; break;
};

}

// To push operators into the final expression

void push(string oper)
{
string empty;
cout << “\nPUSH\n”;

if ( oper == “(” ) {
stack1=stack;
stack=empty;
}
else {
stack = oper + ‘ ‘ + stack;
}

check();
}

// To push whatever in the stack into the final expression

void pop(string oper)
{
int end=0;
string empty;

if (stack.empty() ) cout <<”\nDirectory is Empty\n”;
else {

if ( “)” == oper ) {
postfix = postfix + ‘ ‘ + stack;
stack=stack1;
}
else {
postfix = postfix + ‘ ‘ + stack;
stack = empty; priority=0;
}

cout << “\nPOP\n”;
check();
} // end of else

}

// This function checks to make sure the user input the right amount of parentheses into the expression

// You can also modify this so the user cannot input inappropriate characters

bool error(string expression)
{
int count=0, count1=0, len=expression.length(), a=0, b=0;;

while (a <= len) {
if ( expression[a] == ‘(’ ) {++count;}
++a;
} // end of while

while (b <= len) {
if ( expression[b] == ‘)’ ) {++count1;}
++b;
} // end of while

// execute program if the right amount of parenthesis is avaliable
if (count == count1) return false; else return true;

}