Polish notation, also known as PREFIX or POSTFIX notations, is a form of notation for logic, arithmetic, and algebra. Its distinguishing feature is that it places operators to the left (for prefix) /right (for postfix) of their operands. The Polish logician Jan Łukasiewicz invented this notation around 1920 in order to simplify sentential logic.

The facility of POLISH notation is that we can represent a mathematical expression without any parenthesis or other brackets that can still be parsed without any ambiguity.

If we need to evaluate a mathematical expression programmatically then we can convert the expression into either PRE/POST fix notations and then apply the logic on it for evaluation, that reduces the complexity of evaluation code to a large extent as we don’t require to dig-out the task to be evaluated first on the basis of brackets.

Algorithm to evaluate POSTFIX Notation:

Let S is a stack and PUSH and POP operations are well defined on stack S.

S has been initialized properly.

1.     START OPERATION POSTFIX-EVALUATION (STRING POSTFIX)

2.     WHILE NOT END OF POSTFIX STRING LOOP

3.           SYMB:=NEXT ELEMENT OF POSTFIX STRING

4.           IF SYMB IS AN OPERAND THEN

5.               PUSH SYMB INTO THE STACK

6.           ELSE

7.                OPND1:= POP STACK

8.                OPND2:=POP STACK

9.                RESULT:=APPLY OPERATOR SYMB ON OPND1 AND OPND2

10.            PUSH RESULT INTO THE STACK.

11.       END IF

12.  END LOOP.

13.  VALUE:= POP STACK

14.   RETURN VALUE

15.   END OPERATION POSTFIX-EVALUATION.

.

//Algorithm in C style, courtesy “Data Structure with C and C++ by Tanenbaum”

Let stack is a user defined type and there are standard push and pop operations for the stack type.

while (! end of postfix string){

  symb = next element of the postfix string;

  if(symb is an operand)

   push(stack, symb);

 else{

     opnd2 = pop(stack);

     opnd1 = pop(stack);

     result=operate(opnd1,opnd2, symb);   //operate function returns the result of the arithmetical //operation defined by  symb.

    push(stack, symb);

  }    

 return pop(stack);

}

//***********C Implementation of Evaluating a Single digit PostFix Expression***************//

C Implementation of Evaluating PostFix Expression: EvalPostStringSingle

#include<stdio.h>
#include<stdlib.h>
#include<math.h>

#define SIZE 100
//+++++++++++++++++++Define a stack to hold the operands++++++++++++++//
typedef struct {
double item[SIZE];
int top;
}Stack;

void push(Stack *sp, double value){
if (sp->top == SIZE-1){
printf(“Stack Overflow…xterminating operation\n”);
exit(0);
}
sp->item[++sp->top] = value;
}

double pop(Stack *sp){
if (sp->top == -1){
printf(“Stack Underflow…Terminating operation…”);
exit(0);
}
return sp->item[sp->top–];
}
//++++++++++++END OF STACK DEFINITION+++++++++++++++++//

//**************************Operate function *******************************//

double operate(double left, double right, char opr){
double result=0.0;
switch(opr){
case ‘+’: result=left+right;
break;
case ‘-‘: result=left-right;
break;
case ‘*’: result=left * right;
break;
case ‘/’:result=left/right;
break;
case ‘$’: result=pow(left,right);
break;
default:printf(“Invalid operator encountered…”);
exit(0);

}
return result;
}
//********************END OF OPERATE FUNCTION *********************************//
//58-98*/
double evaluatePostfix(char postfix[]){
Stack s;
int i;
double opnd1, opnd2, result;
char symb;
s.top = -1;
i = 0;
while(postfix[i]!=”){//iterate thru the postfix string till NULL
symb = postfix[i];
if(symb>=48 && symb<=57){
push(&s,(double)(symb-48));
}
else if(symb==’+’ || symb==’-‘ || symb==’*’ || symb==’/’ || symb==’$’){
opnd2 = pop(&s);
opnd1 = pop(&s);
result = operate(opnd1, opnd2,symb);
push(&s, result);
}
else{
printf(“Invalid symbol encountered…\nterminating program…\n”);
exit(0);
}
i++;
}
return pop(&s);
}
////—————————–END EVALUATE FUNCTION———————-//

int main(){
char postfix[SIZE];
printf(“Enter a postfix string: “);
scanf(“%s”,postfix);
printf(“Value of the postfix string: %lf\n”,evaluatePostfix(postfix));
getch();
return 0;
}

//***********C Implementation of Evaluating a Single digit PostFix Expression***************//

.

//***********C Implementation of Evaluating a multiple digit PostFix Expression***************//

C Implementation of Evaluating a PostFix Expression: EvalMulPostString

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<math.h>

#define SIZE 100

typedef struct{
double item[SIZE];
int top;
}Stack;

void push(Stack *sp, double value){
if(sp->top == SIZE -1){
printf(“\nStack Overflow…”);
return;
}
sp->item[++sp->top] = value;
}

double pop(Stack *sp){
if(sp->top == -1){
return -9999;
}
return sp->item[sp->top–];
}

double operate(double val1, double val2, char opr){
double result;
switch(opr){
case ‘+’ : result= val1+val2;
break;
case ‘-‘ : result= val1-val2;
break;
case ‘*’ : result= val1*val2;
break;
case ‘/’ : result= val1/val2;
break;
case ‘$’ : result= pow(val1,val2);
break;
default: printf(“\nInvalid Operator, terminating the process…”);
getch();
exit(0);
}
return result;
}
double evaluate(char postfix[]){
int i,j;
char element[20]; double val1, val2, res;
double k;
Stack stack;
stack.top = -1;
i = 0;
//postfix ->   12,65,+,80,-
//                    i
//element      +
//             j
//stack ->     12.00 65.00
while(1){
j = 0;
while(postfix[i]!=’,’ && postfix[i]!=”){
element[j++] = postfix[i++];
}
element[j] = ”;
k = atof(element);
if (k!=0){//symb is an operand
push(&stack,k);
}
else if(element[0]==’0′){
push(&stack, 0.00);
}
else{
val2 = pop(&stack);
val1 = pop(&stack);
res = operate(val1, val2, element[0]);
push(&stack, res);
} //end of else
if(postfix[i] == ”)
break;
i++;

}//end of while
return pop(&stack);
}//end of function evaluate

void main(){
char postfix[SIZE];
clrscr();
printf(“\nEnter a postfix string: “);
scanf(“%s”,postfix);
printf(“\nprocessing please wait: “);
printf(“\nThe value of the given expression: %lf”, evaluate(postfix));
getch();
}

//***********C Implementation of Evaluating a Mulple digit PostFix Expression***************//

.

Algorithm to evaluate PREFIX Notation:

Let S is a stack and PUSH and POP operations are well defined on stack S.

Let Len is the length of the Prefix String.

S has been initialized properly.

1.     START OPERATION PREFIX-EVALUATION (STRING PREFIX)

2.     WHILE Len is Greater Than Zero

3.           SYMB:=PREFIX[Len]

4.           IF SYMB IS AN OPERAND THEN

5.               PUSH SYMB INTO THE STACK

6.           ELSE

7.                OPND2:= POP STACK

8.                OPND1:=POP STACK

9.                RESULT:=APPLY OPERATOR SYMB ON OPND1 AND OPND2

10.            PUSH RESULT INTO THE STACK.

11.       END IF

12.  END LOOP.

13.  VALUE:= POP STACK

14.  Decrement Len by 1

15.   RETURN VALUE

16.   END OPERATION PREFIX-EVALUATION.

.

//***********C Implementation of Evaluating a Single digit PreFix Expression***************//

C Implementation of Evaluating a Single digit PreFix Expression: SingleDigitPrefixEval
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>

#define SIZE 100

//+++++++++++Define a stack to hold the operands++++++++++//
typedef struct {
double item[SIZE];
int top;
}Stack;

void push(Stack *sp, double value){
if (sp->top == SIZE-1){
printf(“Stack Overflow…xterminating operation\n”);
exit(0);
}
sp->item[++sp->top] = value;
}

double pop(Stack *sp){
if (sp->top == -1){
printf(“Stack Underflow…Terminating operation…”);
exit(0);
}
return sp->item[sp->top–];
}
//+++++++++END OF STACK DEFINITION+++++++++++++++++//

//*************Operate function *******************//

double operate(double left, double right, char opr){
double result=0.0;
switch(opr){
case ‘+’:result=left+right;
break;
case ‘-‘:result=left-right;
break;
case ‘*’:result=left * right;
break;
case ‘/’:result=left/right;
break;
case ‘$’:result=pow(left,right);
break;
default:printf(“Invalid operator encountered…”);

exit(0);

}
return result;
}
//**********END OF OPERATE FUNCTION ******************//

double evaluatePrefix(char prefix[]){
Stack s;
int i,len;
double opnd1, opnd2, result;
char symb;
s.top = -1;
len=strlen(prefix);
len–;

while(len>=0){
symb = prefix[len];
if(symb>=48 && symb<=57){
push(&s,(double)(symb-48));
}
else if(symb==’+’ || symb==’-‘ || symb==’*’ || symb==’/’ || symb==’$’){
opnd2 = pop(&s);
opnd1 = pop(&s);
result = operate(opnd2,opnd1,symb);
push(&s, result);

}
else{
printf(“Invalid symbol encountered…\nterminating program…\n”);
exit(0);
}
len–;
}
return pop(&s);
}
////————–END EVALUATE FUNCTION—————–//

void main(){
char prefix[SIZE];
clrscr();
printf(“Enter a prefix string: “);
scanf(“%s”,prefix);
printf(“Value of the prefix string: %lf\n”,evaluatePrefix(prefix));
getch();
// return 0;

}

//***********C Implementation of Evaluating a Single digit PreFix Expression***************//

.

//***********C Implementation of Evaluating a Multiple digit PreFix Expression***************//

C Implementation of Evaluating a Multiple digit PreFix Expression: MulDigitPrefixEval
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<math.h>

#define SIZE 100

typedef struct{
char item[SIZE];
int top;
}Stack;

void push(Stack *sp, char value){
if(sp->top == SIZE -1){
printf(“\nStack Overflow…”);
return;
}
sp->item[++sp->top] = value;
}

char pop(Stack *sp){
if(sp->top == -1){
return ”;
}
return sp->item[sp->top–];
}

double operate(double val1, double val2, char opr){
double result;
//   printf(“\nopr=%c”,opr);
//   printf(“val1=%lf”,val1);
//   printf(“val2=%lf”,val2);
switch(opr){
case ‘+’ : result= val1+val2;
break;
case ‘-‘ : result= val1-val2;
break;
case ‘*’ : result= val1*val2;
break;
case ‘/’ : result= val1/val2;
break;
case ‘$’ : result= pow(val1,val2);
break;
default: printf(“\nInvalid Operator, terminating the process…”);
getch();
exit(0);
}
return result;
}

double evaluate(char prefix[]){
int i,j;
char element[20];
double val1=-9999, val2=-9999, res, val=0;
double k;
Stack stack;
char x;
stack.top = -1;
i = 0;

while(1){
j = 0;
while(prefix[i]!=’,’ && prefix[i]!=”){
element[j++] = prefix[i++];
//    printf(“\nelement[%d]=%c”,j-1,element[j-1]);
}
element[j] = ”;
val=atof(element);
//       printf(“\n%lf”,val);
if(val!=0)
{
//       printf(“\nval=%lf”,val);
if(val1==-9999)
{
val1=val;
//        printf(“val1=%lf”,val1);
}
else if(val1!=-9999 && val2==-9999)
{

val2=val;
//        printf(“val2=%lf”,val2);
x=pop(&stack);
//        printf(“%c”,x);
val1=operate(val1,val2,x);
val2=-9999;
}

}

else{//symb is an operator
//       printf(“\nk=0=%c”,element[j-1]);
push(&stack, element[j-1]);
}

if(prefix[i] == ”)                //end of string
break;

i++;

}//end of while

return val1;
}//end of function evaluate

void main(){
char prefix[SIZE];
//system(“cls”);
clrscr();
printf(“\nEnter a prefix string: “);
scanf(“%s”,prefix);
printf(“\nprocessing please wait: “);
printf(“\nThe value of the given expression: %lf”, evaluate(prefix));
getch();
}

//***********C Implementation of Evaluating a Multiple digit PreFix Expression***************//

.

Convert the following infix string to its postfix equivalent showing the each steps using a stack. You need to show the status of the stack at each step.

Infix string:   a*(b+c$(k/p))-(m+x)/s

Next Character of Infix String

Stack

Postfix String

comments

UNDERFLOW

Initial State

a

UNDERFLOW

a

a is operand, thus added to the postfix string

*

*

a

Is operator thus pushed into the stack as the stack was empty

(

*, (

a

prcd(*,( ) = FALSE, ( is pushed for the next operator.

b

*, (

ab

b is operand , added to postfix string

+

*, (, +

ab

prcd((,+) = FALSE

c

*, (, +

abc

C is operand

$

*, (, +, $

abc

prcd(+,$) = FALSE

(

*, (, +, $, (

abc

prcd($,( ) = FALSE

k

*, (, +, $, (

abck

K is operand

/

*, (, +, $, (, /

abck

prcd( (,/  ) = FALSE

p

*, (, +, $, (, /

abckp

p is operand, thus pushed

)

*, (, +, $, (

abckp/

prcd( /,) ) = TRUE, / is poped out and appended to the postfix string.

*, (, +, $

abckp/

prcd( (,) ) = FALSE, ( is pop out and discarded

)

*, (, +

abckp/$

prcd( $, ) ) = TRUE, $ poped and appended to the postfix string

*, (

abckp/$+

prcd( +, ) ) = TRUE, + poped and appended to the postfix string

*

abckp/$+

prcd( (,) ) = FALSE, ( is pop out and discarded

UNDERFLOW

abckp/$+*

prcd(*,-) = TRUE, * is pop out and appended with the postfix string.

abckp/$+*

Stack is empty, – is pushed into the stack for checking the next operator.

(

-, (

abckp/$+*

prcd(-,( ) = FALSE, ( is pushed for the next operator.

m

-, (

abckp/$+*m

m is operand, thus pushed.

+

-, (, +

abckp/$+*m

prcd((,+ ) = FALSE, + is pushed for the next operator.

x

-, (, +

abckp/$+*mx

X is operand, thus pushed

)

-, (

abckp/$+*mx+

prcd(+,) ) = TRUE, + is pope out and appended to the postfix string.

abckp/$+*mx+

prcd( (,) ) = FALSE, ( is pope out and discarded

/

-, /

abckp/$+*mx+

prcd(-,/) = FALSE, / is pushed into the stack for the comparing with the next operator to come.

s

-, /

abckp/$+*mx+s

S is operand , thus append s to postfix string

END OF INFIX STRING

abckp/$+*mx+s-

Pop stack and append operator to the postfix string until UNDERFLOW.

UNDERFLOW

abckp/$+*mx+s-/

RESULT.

.

Algorithm to convert INFIX to  POSTFIX Notation:

TRADITIONAL STYLE

prcd(opr1, opr2) checks the precedence of opr1 with respect to opr2, and returns Boolean result, that is if the opr1 has higher precedence than opr2 then prcd returns true otherwise returns false.

Thus a call like prcd(‘*’,’+’) returns true

prcd(‘-’,’$’) returns false.

prcd(operator,’(’) returns false

prcd(‘(’,operator) returns false

prcd(operator, ‘)’) returns true except operator=’(’, in that case previous case is followed.

push() and pop() are standard stack operations.

….

1.    START OPERATION CONVERT INFIX TO POSTFIX (STRING INFIX)

2.    WHILE NOT END OF INFIX STRING LOOP

3.        SYMB:= NEXT ELEMENT OF INFIX STRING

4.        IF SYMB IS AN OPERAND THEN

5.                APPEND SYMB TO THE POSTFIX STRING

6.        ELSE

7.          WHILE  (NOTEMPTY(STACK) AND PRCD(STACKTOP(STACK),SYMB) ) LOOP

8.               TOPSYMB:=POP(STACK)

9.               APPEND TOPSYMB TO THE POSTFIX STRING

10.       END LOOP

11.      IF SYMB==’)’

12.            POP(STACK)

13.     ELSE

14.            PUSH(STACK, SYMB)

15.     END IF

16.  END LOOP

17.  WHILE NOTEMPTY(STACK) LOOP

18.       TOPSYMB:=POP(STACK)

19.      APPEND TOPSYMB TO THE POSTFIX STRING

20.   END LOOP

21.  END OPERATION

.

C Style Algorithm , courtesy “Data structure with C and C++ by Tanenbaum”

while (not end of the infix string){

  if (symb is an operand)

     append symb into the postfix string;

  else (symb is an operator){

    while(!empty(stack) && prcd(stacktop(stack),symb)){   //stack is not empty and stacktop //has an operator having higher preceedance than symb.

          topsymb = pop(stack); //then pop the stack and append the operator to the postfix //string

          append topsymb to the postfix string;

            }

          if (symb!=’)’)

                   push(stack, symb);//if symb not a ) then push it

           else

                   pop(stack);

   }    

}

while(!empty (stack)){

  topsymb = pop(stack);

  append topsymb to postfix string;

}

prcd(opr1, opr2) checks the precedence of opr1 with respect to opr2, and returns Boolean result, that is if the opr1 has higher precedence than opr2 then prcd returns true otherwise returns false.

Thus a call like prcd(‘*’,’+’) returns true

prcd(‘-’,’$’) returns false.

prcd(operator,’(’) returns false

prcd(‘(’,operator) returns false

prcd(operator, ‘)’) returns true except operator=’(’, in that case previous case is followed.

push() and pop() are standard stack operations.

.

//***********C Implementation of converting Infix to PostFix Expression***************//

C Implementation of converting Infix to PostFix Expression: ConvertInfixToPostfix

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<math.h>

#define SIZE 100

/***** Stack to hold the operators for the conversion routine *****/
typedef struct{
char item[SIZE];
int top;
}OprStack;

void push_opr(OprStack *sp, char value)
{
if(sp->top == SIZE -1)
{
printf(“\nStack Overflow…”);
return;
}
sp->item[++sp->top] = value;
}

char pop_opr(OprStack *sp)
{
if(sp->top == -1)
return -9999;

return sp->item[sp->top–];
}
/*******  End of the stack operation  *************/

typedef enum{
FALSE, TRUE
}Boolean;

/*** Following is the prcd function to check the preceedance of 2 operators ***/
//following convension have been taken for checking the brackets
//prcd(op,'(‘)=FALSE;
//prcd(‘(‘,op)= FALSE;
//prcd(op,’)’)= TRUE;
//except op = ‘(‘ in that case FALSE

//[2+{5-(6*5-12)}/4]

Boolean prcd(char left, char right)
{
if (left == ‘(‘ || right == ‘(‘)
return FALSE;
if (left == ‘{‘ || right == ‘{‘)
return FALSE;
if (left == ‘[‘ || right == ‘[‘)
return FALSE;

if (right == ‘)’||right == ‘}’||right == ‘]’)
return TRUE;

if (left == ‘+’ || left == ‘-‘)
{
if (right == ‘+’ || right == ‘-‘)
return TRUE;
else
return FALSE;
}

else if(left == ‘*’ || left == ‘/’)
{
if (right == ‘*’ || right == ‘/’||right == ‘+’ || right== ‘-‘)
return TRUE;
else
return FALSE;
}

else if(left == ‘$’)
{
if (right == ‘$’)
return FALSE;
else
return TRUE;
}
}

/****end of prcd function****/

void convert(char infix[], char postfix[])
{
OprStack stack;
int i=0, j=0;
stack.top = -1;

while(infix[i]!=”)
{
if (infix[i]>=’0′ && infix[i]<=’9′)
{//symb is an operand, need to appent with the postfix string
while(infix[i]>=’0′ && infix[i]<=’9′)
{
postfix[j++] = infix[i++];
}
postfix[j++] = ‘,’;
}
else
{
while(stack.top!=-1 && prcd(stack.item[stack.top],infix[i]))
{
postfix[j++] = pop_opr(&stack);
postfix[j++] = ‘,’;
}

if (infix[i]==’)’||infix[i]==’}’ || infix[i]==’]’)
pop_opr(&stack);
else
push_opr(&stack,infix[i]);

i++;
}//end of else
}//end of while

while(stack.top!=-1){
postfix[j++] = pop_opr(&stack);
postfix[j++] = ‘,’;
}
postfix[j-1] = ”;
}

void main()
{
char infix[SIZE], postfix[SIZE];
clrscr();
printf(“\nEnter the infix expression: “);
scanf(“%s”,infix);
convert(infix, postfix);
printf(“\nEquivalent postfix expresion: %s”,postfix);

getch();
}

//***********C Implementation of converting Infix to PostFix Expression***************//

Advertisements