Chapter 5, Problem 26E

Program Plan Intro

Interpreter:

• Interpreter executes each statement of a program at a time.
• It calls recursive functions for “statement”, “expression”, “factor”, “term” and “Identifier” to execute a statement.
• It allows arithmetic operations addition, subtraction, multiplication, division and exponentiation.

Program Description Answer

/***********************************************************

* This program extends the interpreter with exponentiation *

* process.                                                 *

***********************************************************/

Explanation of Solution

//interpreter.h

//Include header files

#ifndef INTERPRETER

#define INTERPRETER

#include <iostream>

#include <list>

#include <algorithm> // find

using namespace std;

//Definition of class IdNode

class IdNode

{

  //Declare public methods

  public:

  //Declare Parameterized constructor

  IdNode(char *s = "", double e = 0)

  {

  //Initialize variables

  id = strdup(s);

  value = e;

  }

  //Function to overload operator ==

  bool operator== (const IdNode& node) const

  {

/*Return true if both string are same, otherwise return false*/

return strcmp(id,node.id)==0;

  }

  //Declare private variables and overloading function

  private:

  //Declare variables

  char *id;

  double value;

  //Declare class object

  friend class Statement;

  //Prototype for overloading function

friend ostream& operator<<(ostream&, const IdNode&);

};

//Definition of class Statement

class Statement

{

  //Declare public functions

  public :

  //Constructor

  Statement(){}

  //Declare function getStatement()

  void getStatement();

  //Declare private variables

  private:

  //Declare variables

  list<IdNode>idList;

  char ch;

  //Function prototypes

  double factor();

  double term();

  double expression();

  double exponent();

  void readId(char*);

  //Declare function to print error message

  void issueError(char* s)

  {

  cerr << s << endl; exit(1);

  }

  //Function prototypes

  double findValue(char*);

  void processNode(char*, double);

friend ostream& operator<< (ostream&, const Statement&);

};

#endif

//interpreter.cpp

//Include header files

#include <cctype>

#include <stdio.h>

#include <string.h>

#include <string>

#include <list>

#include "interpreter.h"

//Function to find value of identifier

double Statement::findValue(char *id)

{

  //Create object of class IdNode for id

  IdNode tmp(id);

/*If identifier is present in IdNode list, return position */

list<IdNode>::iterator i = find(idList.begin(),idList.end(),tmp);

//If position is not end of list

if (i != idList.end())

//Return value of identifier

return i->value;

//Otherwise

else

//Print error message

issueError("Unknown variable");

// This statement will never be reached;

  return 0;

}

//Function to process node

void Statement::processNode(char* id,double e)

{

/*Create object of class for IdNode for statement*/

IdNode tmp(id,e);

//If identifier is present in IdNode list find position of identifier

list<IdNode>::iterator i = find(idList.begin(),idList.end(),tmp);

//If position of identifier is not end of IdNode list

  if (i != idList.end())

  //Set value of identifier as value of expression

  i->value = e;

  //Otherwise

  else

  //Insert New value into list

  idList.push_front(tmp);

}

/* readId() reads strings of letters and digits that start with a letter, and stores them in array passed to it as an actual parameter.*/

/* Examples of identifiers are: var1, x, pqr123xyz, aName, etc.*/

//Function to read identifier

void Statement::readId(char *id)

{

  //Initialize variable i as 0

  int i = 0;

  //If ch is space

  if (isspace(ch))

  //Skip balks and read next character

  cin >> ch;

  //If character is alphabet

  if (isalpha(ch))

  {

  //Read character till read a non-alphanumeric

  while (isalnum(ch))

  {

  //Copy each character to identifier

  id[i++] = ch;

  //Read next character

  cin.get(ch);

  }

  //Set last character as end of string

  id[i] = '\0';

  }

  //Otherwise

  else

  //Print error message

  issueError("Identifier expected");

}

//Function to find exponent

double Statement::exponent()

{

  // <exponent> ::= <factor> ^ <exponent>,

  double f = factor();

  //If ch is operatotr ^

  if (ch == '^')

  //Compute power and Return it

  return pow(f,exponent());

  //Otherwise

  else

  //Return f

  return f;

}

//Function factor()

double Statement::factor()

{

  //Declare variables

  double var, minus = 1.0;

  static char id[200];

  //Read character

  cin >> ch;

  //If ch is operator + or -

  while (ch == '+' || ch == '-')

  {

  // take all '+'s and '-'s.

  //If ch is -

  if (ch == '-')

/*Set value as negative by multiplying with -1*/

  minus *= -1.0;

  //Read next character

  cin >> ch;

  }

//If ch is digit or operator dot

  if (isdigit(ch) || ch == '.')

  { // Factor can be a number

  //Read digits of number

  cin.putback(ch);

  cin >> var >> ch;

  }

  //If ch is paranthesis (

  else if (ch == '(')

  {

  // or a parenthesized expression,

  //Get next expression after (

  var = expression();

  //If character is )

  if (ch == ')')

  //Read next character

  cin >> ch;

  //Otherwise

  else

  //Print error message

issueError("Right paren left out");

  }

  //Otherwise

  else

  {

  //Read identifier

  readId(id);

  //If chracter is space

  if (isspace(ch))

  //Read next character

  cin >> ch;

  //Get value of identifier

  var = findValue(id);

  }

  //Return value

  return minus * var;

}

//Function for term()

double Statement::term()

{

  //Call function exponent()

  double f = exponent();

  //Do calculation for operators * and /

  while (true)

  {

  //Switch statement

  switch (ch)

  {

  //If ch is *, multiply recursively

  case '*' : f *= exponent(); break;

  //If ch is *, divide recursively

  case '/' : f /= exponent(); break;

  //Defaultly return f

  default : return f;

  }

  }

}

//Function for expression()

double Statement::expression()

{

  //Call function term()

  double t = term();

  //Do calculation for operators + and -

  while (true)

  {

  //Switch statement

  switch (ch)

  {

  //If ch is +, add recursively

  case '+' : t += term(); break;

  //If ch is -, subtract recursively

  case '-' : t -= term(); break;

  // Return f

  default : return t;

  }

  }

}

//Function to read statement

void Statement::getStatement()

{

  //Declare variables

  char id[20], command[20];

  double e;

  //Prompt and read statement

  cout << "Enter a statement: ";

  cin >> ch;

  //Read identifier

  readId(id);

  //Copy identifier to string command

  strupr(strcpy(command,id));

  //If command is STATUS

  if (strcmp(command,"STATUS") == 0)

  //Print current values of all variables

  cout << *this;

  //If command is PRINT

  else if (strcmp(command,"PRINT") == 0)

  {

  //Read identifier from user

  readId(id);

  //Get value of identifier and print it

  cout << id << " = " << findValue(id) << endl;

  }

  //If command is END

  else if (strcmp(command,"END") == 0)

  //Retun from program

  exit(0);

  //Otherwise

  else

  {

  //If ch is space

  if (isspace(ch))

  //Read next character

  cin >> ch;

  //If ch is =

  if (ch == '=')

  {

  //Read expression

  e = expression();

  //If ch is not ;

  if (ch != ';')

  //print error message

issueError("There are some extras in the statement");

//Otherwise process statement

else processNode(id,e);

}

//Otherwise print error message

else issueError("'=' is missing");

}

}

/*Function to overload operator << to print values all identifiers in list*/

ostream& operator<< (ostream& out, const Statement& s)

{

  //Initialize iterator

  list<IdNode>::const_iterator i = s.idList.begin();

  //For each identifier

  for ( ; i != s.idList.end(); i++)

  //Print value of identifier

  out << *i;

  //Print new line

  out << endl;

  return out;

}

/*Function to overload operator << to print value od identifier*/

ostream& operator<< (ostream& out, const IdNode& r)

{

  //Print value of identifier

  out << r.id << " = " << r.value << endl;

  return out;

}

//useInterpreter.cpp

//Include header files

#include "interpreter.h"

using namespace std;

//Program begins with main()

int main()

{

  //Declare object of class Statement

  Statement statement;

  //Prompt message

cout << "The program processes statements of the following format:\n"<< "\t<id> = <expr>;\n\tprint <id>\n\tstatus\n\tend\n\n";

// This infinite loop is broken by exit(1)

  while (true)

  // in getStatement() or upon finding an

  statement.getStatement();

  //Return 0

  return 0;

}

Explanation:

• Define function “exponent()” as member of class “Statement”.
• In function “exponent()”,
  • It calls function “factor()”
  • If next character is “^” compute exponentiation by calling function itself recursively.
  • Return result.
• Function “term()” calls function “exponent()” instead of “factor()”.

Sample Output

Output:

The program processes statements of the following format:

  <id> = <expr>;

  print <id>

  status

  end

Enter a statement: var1=2+(2^3);

Enter a statement: var2=var1-2;

Enter a statement: var3=var2*2;

Enter a statement: status

var3 = 16

var2 = 8

var1 = 10

Enter a statement: var3=var3-4;

Enter a statement: print var3

var3 = 12

Enter a statement: end