Infix Expressions

CS  340  Fall  2015   Assignment  2  

  Due 09/27/15

Assignment  2  

•  Modify  the  infix  evaluaDon  program  so  it  processes   assignment  statements  where  the  expressions  can   contain  variables.  A  variable  will  be  a  string  of  1  to  6   alphabeDc  characters.  

•  The  values  of  variables  must  be  stored  in  a  symbol   table  that  is  stored  in  a  binary  file.  The  symbol  table   should  be  stored  as  a  sorted  (based  on  the  variable)   sequence.  To  find  the  value  of  variable  the  program   must  search  the  symbol  table  using  a  binary  search.  I   will  review  binary  search  in  class  and  give  an  example   using  an  ArrayList  

Assignment  2  

•  All  accesses  (looking  up  the  current  value,   giving  a  variable  a  new  value,  etc)  to  the   symbol  table  must  use  the  binary  file.  That  is   you  cannot  just  read  in  the  contents  of  the  file   into  memory  (e.g.  into  an  ArrayList)  and  then   access  this  informaDon  from  the  ArrayList.  

•  UniniDalized  variables  are  assumed  to  have   the  value  0.    

Assignment  2  

•  The  program  expects  two  command  line   arguments.  The  first  argument  is  the  name  of  a   text  file  that  contains  one  assignment  statement   per  line.  The  second  command  line  argument  is   the  name  of  the  binary  file  that  will  be  used  to   store  the  symbol  table  

•  As  in  assignment  one  the  tokens  in  the   assignment  statements  will  be  separated  by   whitespace.  

•  You  can  assume  the  input  is  syntacDcally  correct  

Assignment  2  

•  AUer  all  the  lines  in  the  input  file  have  been   evaluated  the  program  should  print  the   contents  of  the  symbol  table  

Assignment  2   Example  Input  File  

X  =  10   xsqr  =  X  ^  2   w  =  y  +  3  *  z   y  =  2   z  =  2  *  (  X  +  y  )  ^  (X  –  8)  

Example  Output  

Id      Value   X      10   w      0   xsqr    100   y      2   z      288    

Symbol  Table  

public  class  SymbolTable  {   //we  will  learn  beaer  ways  (such  as  a  hash  table)  to  do  this     //but  for  now  we  will  store  values  in  a  sorted  sequence    

 private  class  Item  {      String  id;      int  value;  

     Item(String  i,  int  v)  {        id  =  i;        value  =  v;          }  

     String  getId()  {        return  id;      }  

Symbol  Table  

   int  getValue()  {        return  value;      }  

     void  setId(String  i)  {        id  =  i;      }  

     void  setValue(int  v)  {        value  =  v;      }    }  

Symbol  Table    ArrayList<Item>  table;    int  place;      

   public  SymbolTable()  {      table  =  new  ArrayList<>();    }  

   public  void  insert(String  id,  int  v)  {      if  (find(id))        table.get(place).setValue(v);      else        table.add(place,  new  Item(id,v));    }  

Symbol  Table    public  boolean  find(String  id)  {      int  high  =  table.size()-­‐1;      int  low  =  0;      int  mid;      while  (  low  <=  high  )  {        mid  =  (high-­‐low)/2  +  low;  //why  not  (low+high)/2        int  cmp  =  table.get(mid).getId().compareTo(id);        if  (cmp  <  0)            low  =  mid+1;        else  if  (cmp  >  0)          high  =  mid  -­‐  1;        else  {          place  =  mid;          return  true;        }      }      place  =  low;      return  false;    }  

Symbol  Table  

 public  int  getValue()  {      return  table.get(place).getValue();    }  

   public  void  setValue(int  v)  {      table.get(place).setValue(v);  

   }  

   public  void  printTable()  {      System.out.println("Id\tValue");      for  (int  i  =  0;  i  <  table.size();  i++)        System.out.println(table.get(i).getId()+"\t"+table.get(i).getValue());    }  

Symbol  Table  

•  My  implementaDon  of  SymbolTable  is  just  an   example  so  you  can  see  the  basic  operaDons   and  how  binary  search  can  be  used  to  find  the   value  of  a  variable.  You  can  choose  different   methods  if  you  want  but  your  implementaDon   must  have  the  characterisDcs  shown  on  the   next  slide  

Symbol  Table  

•  Data  must  be  stored  and  accessed  in  a  binary   file.  

•  Only  the  most  recently  accessed  item  can  be   stored    in  memory  

•  Items  must  be  stored  sorted  in  ascending   order  based  on  the  variable  id  

•  A  binary  search  must  be  used  to  find  items  

Assignment  Submission  

•  Send  me  only  2  Java  files.  The  files  should  be   called  InfixEval.java  and  SymbolTable.java  

•  The  first  line  in  the  file  should  be  a  comment   with  your  name  in  the  comment  

•  In  the  subject  field  of  the  email  put  the  value   CS340  A2