# 2 Types of Expressions – Postfix and Prefix. Master Rules to Convert.

This post is also available in: العربية (Arabic)

## What is an Arithmetic Expression?

An arithmetic expression is a syntactically correct combination of numbers, operators, parenthesis, and variables. E.g., 34 + 15, 45.78 – 21.89 + 31, -18/7, 2.43^4, 6.52 * (-3) are all arithmetic expressions.

Remember that syntax means the rules for putting together a correctly formed statement. Arithmetic expressions are parts of statements, so must follow syntax rules to be correct.

## 2 Types of Expressions – Postfix and Prefix: Rules for Evaluating Expressions

The following are the rules for evaluating an arithmetic expression:

• Expressions are always evaluated from left to right.
• If an operator is encountered in the process of evaluation, its priority is compared with that of the next one. If the next one is lower, evaluate the current operator with its operands. For example in 2 * 7 – 8, operator * is encountered first. Since ‘-’ is lower, 2 * 7 is evaluated first transforming the expression to 14 – 8. Hence, the result is 6.
• If the next operator is equal to the current operator, the associativity rules are used to determine which one should be evaluated first. For example, if both the current and the next operator are *, then 2 * 3 * 4 will be evaluated as (2 * 3) * 4. On the other hand, if the operator is ^ (raise to the power), then 2 ^ 3 ^ 4 will be evaluated as 2 ^ (3 ^ 4).
• If the next one is higher than the current operator, the scan should continue with the next operator. For example, in 3 + 2 * 3 ^ 2, the first operator is +, and the next operator * has higher priority, the scan continues to *. Once the scan arrives at *, since the next operator ^ is higher, 3^2 is evaluated first, transforming the given expression to 3 + 2 * 9. Then, the new expression is scanned again. The next operator to be evaluated is *, followed by +. Thus the expression becomes 3 + 18, which finally results in 21.

Many times these expressions have brackets – () (Parentheses), {} (Braces) or [] (Square Brackets). In such cases, the inner brackets are evaluated first and then the outer brackets. While evaluating an expression inside the brackets, the above-mentioned rules are followed. For example in the case of [12 – {5 * (3 – 4)}], first of all, 3 – 4 is evaluated inside the brackets ( and ). This results in [12 – {5 * (-1)}]. Now the expression inside { and } is evaluated which results in [12 – (-5)] which is equal to 12 + 5 = 17.

## What are Infix, Postfix, and Prefix Notations?

Infix, Postfix, and Prefix notations are three different but equivalent ways of writing expressions. It is easiest to demonstrate the differences by looking at examples of operators that take two operands. Let’s consider two operands X and Y with one operator ‘+’.

Infix Notation: X + Y

Operators are written in-between their operands. This is the usual way we write expressions.

Postfix Notation (also known as “Reverse Polish notation”): X Y +

Operators are written after their operands.

Prefix Notation (also known as “Polish notation“): + X Y

Operators are written before their operands.

Now, let’s extend it for more than two operands and more than one operator. Let’s consider the operands A, B, C, and D and operators as “*”, “+” and “/”.

### Infix Notation

An expression such as A * ( B + C ) / D is usually taken to mean something like: “First add B and C together, then multiply the result by A, then divide by D to give the final answer.”

Infix notation needs extra information to make the order of evaluation of the operators clear: rules built into the language about operator precedence and associativity, and brackets ( ) to allow users to override these rules. For example, the usual rules for associativity say that we perform operations from left to right, so the multiplication by A is assumed to come before the division by D. Similarly, the usual precedence rules say that we perform multiplication and division before we perform addition and subtraction.

### Postfix Notation

The postfix expression given above is equivalent to A B C + * D /

The order of evaluation of operators is always left-to-right, and brackets cannot be used to change this order. Because the “+” is to the left of the “*” in the example above, the addition must be performed before the multiplication.

Operators act on values immediately to the left of them. For example, the “+” above uses the “B” and “C”. We can add (unnecessary) brackets to make this explicit: ( (A (B C +) *) D /)

Thus, the “*” uses the two values immediately preceding: “A”, and the result of the addition. Similarly, the “/” uses the result of the multiplication and the “D”.

Because Postfix operators use values to their left, any values involving computations will already have been calculated as we go left-to-right, and so the order of evaluation of the operators is not disrupted in the same way as in Prefix expressions.

### Prefix Notation

The expressions given above are equivalent to / * A + B C D.

As for Prefix, operators are evaluated left-to-right and brackets are superfluous. Operators act on the two nearest values on the right. I have again added (unnecessary) brackets to make this clear: (/ (* A (+ B C) ) D)

Although Prefix “operators are evaluated left-to-right”, they use values to their right, and if these values themselves involve computations then this changes the order that the operators have to be evaluated in. In the example above, although the division is the first operator on the left, it acts on the result of the multiplication, and so the multiplication has to happen before the division (and similarly the addition has to happen before the multiplication).

In all three versions, the operands occur in the same order, and just the operators have to be moved to keep the meaning correct. (This is particularly important for asymmetric operators like subtraction and division: A – B does not mean the same as B – A; the former is equivalent to A B – or – A B, the latter to B A – or – B A).

Examples:

### Converting Between These Notations

The most straightforward method is to start by inserting all the implicit brackets that show the order of evaluation e.g.:

You can convert directly between these bracketed forms simply by moving the operator within the brackets e.g. (X + Y) or (X Y +) or (+ X Y). Repeat this for all the operators in an expression, and finally remove any superfluous brackets.

### Steps needed for Infix to Postfix conversion

1. Search the infix string from left to right.
2. Initialize a vacant stack.
3. If the scanned character is an operand add it to the Postfix string.
4. When the scanned character is an operator and if the stack is empty Push the character to stack.
5. If a scanned character is an operator and the stack is not empty, compare the precedence of the character with the element on top of the stack.
6. When the top of a stack has higher precedence over the scanned character pop the stack else Push the scanned character to the stack. Repeat this procedure till the stack is not empty and the top of the stack has precedence over the character.
7. Reiterate 4 and 5 steps till all the characters are scanned.
8. After all the characters are scanned, we add the character that the stack may have to the Postfix string.
9. When a stack is not empty add top of the stack to postfix string and pops the stack.
10. Repeat the process as long as the stack is not empty.

Infix Expression: (A/(B – C) * D + E)

Converted Postfix expression is ABC-/D*E+

### Infix to Postfix conversion using stack in C++

#define MAX 20
char stk;
// Push function here, inserts value in stack and increments stack top by 1
void push(char oper)
{
if(top==MAX-1)
{
cout<<"stackfull!!!!";
}

else
{
top++;
stk[top]=oper;
}
}
// Function to remove an item from stack.  It decreases top by 1
char pop()
{
char ch;
if(top==-1)
{
cout<<"stackempty!!!!";
}
else
{
ch=stk[top];
stk[top]='\0';
top--;
return(ch);
}
return 0;
}
int priority ( char alpha )
{
if(alpha == '+' || alpha =='-')
{
return(1);
}

if(alpha == '*' || alpha =='/')
{
return(2);
}

if(alpha == '\$')
{
return(3);
}

return 0;
}
string convert(string infix)
{
int i=0;
string postfix = "";
while(infix[i]!='\0')
{
if(infix[i]>='a' && infix[i]<='z'|| infix[i]>='A'&& infix[i]<='Z')
{
postfix.insert(postfix.end(),infix[i]);
i++;
}
else if(infix[i]=='(' || infix[i]=='{'  || infix[i]=='[')
{
push(infix[i]);
i++;
}
else if(infix[i]==')' || infix[i]=='}'  || infix[i]==']')
{
if(infix[i]==')')
{
while(stk[top]!='(')
{               postfix.insert(postfix.end(),pop());
}
pop();
i++;
}
if(infix[i]==']')
{
while(stk[top]!='[')
{
postfix.insert(postfix.end(),pop());
}
pop();
i++;
}

if(infix[i]=='}')
{
while(stk[top]!='{')
{
postfix.insert(postfix.end(),pop());
}
pop();
i++;
}
}
else
{
if(top==-1)
{
push(infix[i]);
i++;
}

else if( priority(infix[i]) <= priority(stk[top])) {
postfix.insert(postfix.end(),pop());

while(priority(stk[top]) == priority(infix[i])){
postfix.insert(postfix.end(),pop());
if(top < 0) {
break;
}
}
push(infix[i]);
i++;
}
else if(priority(infix[i]) > priority(stk[top])) {
push(infix[i]);
i++;
}
}
}
while(top!=-1)
{
postfix.insert(postfix.end(),pop());
}
cout<<"The converted postfix string is : "<<postfix; //it will print postfix conversion
return postfix;
}

int main()
{
int cont;
string infix, postfix;
cout<<"\nEnter the infix expression : "; //enter the expression
cin>>infix;
postfix = convert(infix);
return 0;
}


### Steps needed for Infix to Prefix conversion using stack

1. Reverse the expression given for the infix.
2. Scan the characters one by one.
3. If the character is an operand, then copy it to the output of the prefix notation.
4. If the character is a closing parenthesis then push it to the stack.
5. If the character is an opening parenthesis, pop the elements in the stack till we find the closing parenthesis that corresponds.
6. If a character scanned is operator and has greater or equal precedence then push the operator to the stack.
7. If a character scanned is operator and has lower precedence then pop the operator and output it to the output of the prefix notation, then check the above condition with the new top of the stack again.
8. After scanning all the characters, reverse the notation output for the prefix.

Infix Expression: (A/(B – C) * D + E)

Reverse Infix String: )E + D * )C – B( / A(

Reverse the final output: +*/A-BCDE

Converted Prefix expression is +*/A-BCDE

### Infix to Prefix conversion using stack in C++

struct Stack *create (int max);
int stackFull (struct Stack *stack);
int stackEmpty (struct Stack *stack);
void pushElement (struct Stack *stack, int item);
int popElement (struct Stack *stack);
int peekElement (struct Stack *stack);
int checkOperand (char ch);
int precedence (char ch);
int postfix (char *expression);
void reverse (char *exp);
void brackets (char *exp);
void conversionInfixToPrefix (char *exp);
// A structure to represent a stack
struct Stack
{
int top;
int maxSize;
int *array;
};
int main ()
{
int n = 10;
cout << "The infix expression is: \n";
char expression[] = "(P+(Q*R)/(S-T))";
cout << expression << "\n";
conversionInfixToPrefix (expression);
cout << "The prefix expression is: \n";
cout << expression;
return 0;
}
//stack implementation
struct Stack * create (int max)
{
struct Stack *stack = (struct Stack *) malloc (sizeof (struct Stack));
stack->maxSize = max;
stack->top = -1;
stack->array = (int *) malloc (stack->maxSize * sizeof (int));
return stack;
}

// Checking with this function is stack is full or not
int stackFull (struct Stack *stack)
{
if (stack->top == stack->maxSize - 1)
{
cout << "Will not be able to push maxSize reached\n";
}
// We know array index from 0 and maxSize starts from 1
return stack->top == stack->maxSize - 1;
}

// if Stack is empty when top is equal to -1 and return true
int stackEmpty (struct Stack *stack)
{
return stack->top == -1;
}

// Push function it inserts value in stack and increments stack top by 1
void pushElement (struct Stack *stack, int item)
{
if (stackFull (stack))
return;
stack->array[++stack->top] = item;
}

// pop Function it remove an item from stack and decreases top by 1
int popElement (struct Stack *stack)
{
if (stackEmpty (stack))
return INT_MIN;
return stack->array[stack->top--];
}

// Function to return the top from stack without removing it
int peekElement (struct Stack *stack)
{
if (stackEmpty (stack))
return INT_MIN;
return stack->array[stack->top];
}

// A function check the given character is operand
int checkOperand (char ch)
{
return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z');
}

// Fucntion to compare precedence if return larger value means higher precedence
int precedence (char ch)
{
switch (ch)
{
case '+':
case '-':
return 1;

case '*':
case '/':
return 2;

case '^':
return 3;
}
return -1;
}

// The function for infix to postfix conversion
int postfix (char *expression)
{
int i, j;
struct Stack *stack = create (strlen (expression));
if (!stack)
return -1;

for (i = 0, j = -1; expression[i]; ++i)
{
// checking the character we scanned is operand or not
if (checkOperand (expression[i]))
expression[++j] = expression[i];

// if we scan character push it to the stack
else if (expression[i] == '(')
pushElement (stack, expression[i]);

//if we scan character we need to pop and print from the stack
else if (expression[i] == ')')
{
while (!stackEmpty (stack) && peekElement (stack) != '(')
expression[++j] = popElement (stack);
if (!stackEmpty (stack) && peekElement (stack) != '(')
return -1;		// invalid expression
else
popElement (stack);
}
else			// if an operator
{
while (!stackEmpty (stack)
&& precedence (expression[i]) <=
precedence (peekElement (stack)))
expression[++j] = popElement (stack);
pushElement (stack, expression[i]);
}

}

// if all first expression characters are scanned
// adding all left elements from stack to expression
while (!stackEmpty (stack))
expression[++j] = popElement (stack);
expression[++j] = '\0';
}

void reverse (char *exp)
{				//reverse function for expression

int size = strlen (exp);
int j = size, i = 0;
char temp[size];

temp[j--] = '\0';
while (exp[i] != '\0')
{
temp[j] = exp[i];
j--;
i++;
}
strcpy (exp, temp);
}

void brackets (char *exp)
{
int i = 0;
while (exp[i] != '\0')
{
if (exp[i] == '(')
exp[i] = ')';
else if (exp[i] == ')')
exp[i] = '(';
i++;
}
}

void conversionInfixToPrefix (char *exp)
{
int size = strlen (exp);
reverse (exp);
brackets (exp);
postfix (exp);
reverse (exp);
}