19 August 2010

postfix evaluation and checking the balance of the parenthesis

here r the codes for 2 famous problems of programming lab (for 1st yr btech students although i did it in my mtech).The language used here is c++.


1. POSTFIX EVALUATION (I got this problem in the entrance exam of IIIT-A)

#include <iostream.h>
#include <conio.h>
#include <stdio.h>
#include <ctype.h>


float a[30],top=-1;
void push(int val)
{
 if(top==29)
 cout<<"\nOVERFLOW";
 else
 {
  top++;
  a[top]=val;
 }

}

void pop(char c)
{ float temp;
switch(c)
{

case '+':  temp=a[top-1]+a[top];top--;a[top]=temp;break;
case '-':   temp=a[top-1]-a[top];top--;a[top]=temp;break;
case '*':   temp=a[top-1]*a[top];top--;a[top]=temp;break;
case '/':   temp=a[top-1]/a[top];top--;a[top]=temp;break;

}

}


void main()
{  char *p=NULL; int i,s=0; char opt;
do
{ top=-1;
clrscr();
cout<<"\nENTER THE POSTFIX NOTATION(separate operator and operand by a space) : ";
gets(p);
for(i=0;p[i]!=NULL;i++)
{

if(p[i]==' ')
continue;

else if(isdigit(p[i]))
{    while(isdigit(p[i]))
{
  s=s*10+p[i]-'0';
  i++;
}
push(s);
s=0;
}
else
pop(p[i]);
}
cout<<"\nANS IS : "<<a[0];
cout<<"\n\nDO YOU WANT TO CONTINUE(y/n) : ";
cin>>opt;

}while(opt=='y'||opt=='Y');
getch();
}





2. CHECKING THE BALANCE OF THE PARENTHESIS  (I got this problem as a lab test)


#include<iostream.h>
#include<conio.h>
#include<stdio.h>
 

int top=-1; char a[30];
 void push(char p)
 {
 if(top==29)
 cout<<"overflow";
 else
 {top++;
 a[top]=p;
 }

 }

     pop(char p)
{
     switch(p)
     {

     case ')' : if(a[top]=='('){top--;return 1;}
     case '}' : if(a[top]=='{'){top--;return 1;}
     case ']' : if(a[top]=='['){top--;return 1;}


     }
     return 0;

}

void main()
{  char *p=NULL;int i,valid=1;char opt='y';


do
{top=-1;    clrscr();     valid=1;
cout<<"\n\nENTER THE INFIX EXPRESSION : ";
gets(p);
for(i=0;p[i]!=NULL;i++)
{

if(p[i]=='('||p[i]=='{'||p[i]=='[')
push(p[i]);
else if(p[i]==')'||p[i]=='}'||p[i]==']')
{
int chk=pop(p[i]);
if(chk==0)
{valid=0;break;}

}
else
continue;
}

 if(valid==1 && top==-1)
 cout<<"\nbrackets are balanced" ;
 else
 cout<<"\nbrackets are not balanced";
cout<<"\n\ndo you wan to test more(y/n) : ";
cin>>opt;

}while(opt=='y'||opt=='Y');
 getch();
}



NOTE: IF YOU WANT TO DISCUSS ANYTHING RELATED TO C,C++,JAVA(CORE),.NET(C#),DATA STRUCTURE,SQL THEN YOU ARE AT THE CORRECT DOOR....JUST KNOCK IT:)



Delicious add to del.icio.us saved by 0 users

9 comments:

  1. coding is correct but it can be optimized.....

    ReplyDelete
  2. This is mine. Smaller and concise. :P


    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define MAX 100

    int stack[20], b=0;

    void push(int a){
    printf("Pushing %d at position %d\n",a,b);
    stack[b]=a;
    b++;
    }

    int pop(){
    printf("Popping %d from position %d and setting stack top to position %d\n", stack[b-1], b-1, b-1);
    b--;
    return stack[b];
    }

    void operate(char c){
    int temp1, temp2;
    switch(c){
    case '+':
    temp1=pop();
    temp2=pop();
    printf("Adding %d to %d and going to push result %d\n", temp1, temp2, temp2+temp1);
    push((temp2+temp1));
    break;
    case '-':
    temp1=pop();
    temp2=pop();
    printf("Subtracting %d from %d and going to push result %d\n", temp1, temp2, temp2-temp1);
    push((temp2-temp1));
    break;
    case '*':
    temp1=pop();
    temp2=pop();
    printf("Multiplying %d by %d and going to push result %d\n", temp1, temp2, temp2*temp1);
    push((temp2*temp1));
    break;
    case '/':
    temp1=pop();
    temp2=pop();
    printf("Dividing %d into %d and going to push result %d\n", temp2, temp1, temp2/temp1);
    push((temp2/temp1));
    break;
    }
    }

    int main(){
    char *s;
    s=(char *)malloc(MAX*(sizeof(char)));
    fgets(s, MAX, stdin);
    char *p, *q[20];
    int i=0;
    p = strtok(s, " ");
    do{
    q[i] = p;
    p = strtok(NULL, " ");
    i++;
    }while(p!=NULL);
    int j;
    for(j=0;j<i;j++){
    //printf("%d: %s\n",j,q[j]);
    if(isdigit(*q[j])){
    printf("Found %d as a number, pushing it to stack.\n",atoi(q[j]));
    push(atoi(q[j]));
    }
    else{
    printf("Found %c as an operator. Going to operate.\n",*q[j]);
    operate(*q[j]);
    }
    }
    printf("The result is: %d\n",stack[0]);
    return(0);
    }

    ReplyDelete
  3. @prab yur code has 3 errors if compiled as .c file and 1 error if compiled as .cpp file

    ReplyDelete
  4. "ctype.h" header file include karna bhool gaya;)...waise mast code hai yaar.....aadhe se jada code to samajh heee nhe aaya...new fns use kiye hain tune..gud job:)

    ReplyDelete
  5. Abe gcc se compile kar. 20 saal purana compiler, Turbo C use karega toh yahee hoga.

    ReplyDelete
  6. @prab even visual studio is rejectng to compile this mr tech addict

    ReplyDelete
  7. this doesnt handle decimals ;(

    ReplyDelete
  8. well, the original post does, but when i try to compile i get like 9 errors for "illegal use of floating point in function main"

    ReplyDelete