FOR FREE YEAR SOLVED

The expression in which the operator appears in between the operands is known as infix expression. 

For example, (a + b), where a and b are operands, + is an operator that appears between the operands a and b. 

Similarly, the expression in which the operator appears after the operands is known as postfix expression. 

For example, ab+, where a and b are operands, + is an operator that appears after the operands a and b.

Conversion from infix to postfix:

There are some rules for converting an expression from infix to postfix. The rules are:

     1. The infix expression should be scanned from left to right.

     2. If the next symbol is an operand then it will be appended to the postfix string.

     3. If the next symbol is an operator-

            i. The operators (above the most recently found left parenthesis) will be popped from the stack and appended to the postfix expression or the operators which have the higher precedence or is a right-associative operator of equal precedence to the new operator.

            ii. The new operator will be pushed onto the stack.

     4. If the symbol is a left parenthesis, it is pushed onto the stack.

    5. If the symbol is a right parenthesis then all the operators up to the most recently scanned left parenthesis will be popped and will be appended to the postfix string. And the pair of parenthesis will be discarded

    6. After scanning the infix string, if the stack contains any operators will be popped and will be appended to the postfix string.

Let the expression be:  A+B*C/D-E

Now the stack can be used to evaluate the expression as:

INPUT: An infix String
OUTPUT: A postfix string
Step 1: [Declaration of the global variables]
	An array of characters named ‘stack’
	An integer variable ‘top’ initialized to -1.
Step 2: [Function ‘push(character x )’]
	Set top<-top+1
	Set stack[top]<-x
[End of ‘push()’]
Step 3: [Function ‘pop()’ which returns a character]
	Return stack[top]
	Set top<-top-1
[End of function ‘pop()’]
Step 4: [Function ‘precedence(character c)’ returns an integer]
    	If c = '+' or c='-' then
        		return 1
        	else if c = '*' or  c = '/' then
        		return 2
   	else if c = '^' then
        		return 3
    	else
    		return -1
[End of function ‘precedence()’]
Step 5: [function ‘main()’]
	Read a [the infix expression]
        	Print "The postfix expression is: "
    	For i=0 to length(a)-1 repeat
       		Set c<-a[i]
       		If precedence(c)>0 then
       		 	While top≠-1 and precedence(stack[top])≥precedence(c) repeat
                    			Print pop()
            			[End of ‘while’ loop]
            			Push c
	   	[End of ‘if’]
	   	else if c=')' then
	   		Set x<-pop()
	   		While x≠'(' repeat
	   			Print x
				Set x<-pop()	
			[End of ‘while’ loop]
	   	[End of ‘else if’]
	   	else if c='(' then
	   		push(c)
		[End of ‘else if’]
	   	else
	   		print c
		[End of ‘else’]
    	[End of ‘for’ loop]
    	For i=0 to top+1 repeat
    		Print pop()
	[End of ‘for’ loop]
[End of ‘main’ function]