Tokenizer in Linked List
The following is a program of one student who implemented successful the tokenizer. However, the class is not clean to be used by other classes. Then you will see a major modified version. Many unnecessary variables and structures are removed. Here are some general commonest:
- The original program has a bug on the link tokenPre.
- It does not handle the hidden token multiplication in the case of 125x or x125.
- Attributes and constructors should be built to alleviate the burden on the main program. The main program suppose to be a testing or guideline for the class.
- Many sections of codes are repeating. They should be moved to a method as a single copy so that it can be centralized for modification.
- The constants for the token type 0-9 should be centralized as well. Instead using the values, implementers should used the constant statement to code them such as
CONST MULT = 4;
CONST PLUS = 2;
Two appendices are given:
- A modified version of Tokenizer
- The stack to be implemented in linked list.
Appendix A.
//Modified
//11-23-99
// source inpostfix.java
// infix order to postfix order
import java.io.*;
import java.lang.*;
import java.util.*;
class TokenAndType
{
// a pair as attributes
String token;
int type;
//constructor
public TokenAndType()
{
token = null;
type = -1; // means no type
} // end of contructor
public TokenAndType(String tokenName,int tokenType)
{
token = tokenName;
type = tokenType;
} // end of contructor
public void printTokenPair()
{
System.out.print("token pair: " + token + " " + type);
}
} // end of class
class NodePtr
{
// Attributes of any member of NodePtr
TokenAndType tokenPair;
NodePtr next;
// Constructor to insert the node at the top of inputNodePtr
public NodePtr(TokenAndType tokenPair, NodePtr next)
{
this.tokenPair = tokenPair;
this.next = next;
}
public NodePtr()
{
tokenPair = new TokenAndType();
next = null;
}
public NodePtr( String tokenName,int tokenType)
{
tokenPair = new TokenAndType(tokenName, tokenType);
next = null;
}
}
class Tokenizer
{
// attributes
NodePtr top = null; // this is the tokenStream in Linked list
// method
public void GetTokens()
{
NodePtr temp = null;
NodePtr last = null; // points to the last node
String token="";// from string of characters, cut into 1 token
// at a time
InputStreamReader reader = new InputStreamReader (System.in);
BufferedReader console = new BufferedReader (reader);
System.out.print("please enter data> ");
String StrExp = null;
try
{
StrExp = console.readLine();
}
catch (IOException e)
{
System.out.println("we call an" + e);
System.exit(1);
}
char firstChar=' ';
if (StrExp.length()!=0)firstChar = StrExp.charAt(0);
while(StrExp!=null)
{
switch (firstChar)
{
case '.': case '0': case '1': case '2': case '3':
case '4': case '5': case '6': case '7': case '8': case '9':
do {
token=token+firstChar;
if (StrExp.length()==1){StrExp = null;}
else
{
StrExp=StrExp.substring(1);
firstChar = StrExp.charAt(0);
}
}while( ((firstChar >='0' & firstChar <= '9')
|| firstChar == '.')
& StrExp != null);
//create a new node
temp = new NodePtr(token, 3);
// link to top and last
if (last == null) // no node
{ top = temp;
last = temp; }
else { last.next = temp;
last = temp; }
token = ""; // to reset
break;
case' ':
while(firstChar==' ')
{
if (StrExp.length()==1){StrExp = null;}
else
{
StrExp=StrExp.substring(1);
firstChar = StrExp.charAt(0);
}
}
break;
case 'x': case '(': case ')':
case '+': case '-': case '*':
case '/':
if (firstChar == 'x')
{ temp = new NodePtr("x", 4);}
else if (firstChar == '(')
{ temp = new NodePtr("(", 1);}
else if (firstChar == ')')
{ temp = new NodePtr(")", 2);}
else if (firstChar == '+')
{ temp = new NodePtr("+", 5);}
else if (firstChar == '-')
{ temp = new NodePtr("-", 6);}
else if (firstChar == '*')
{ temp = new NodePtr("*", 7);}
else { temp = new NodePtr("/", 8);}
// insert here
if (last == null) // no node
{ top = temp;
last = temp; }
else { last.next = temp;
last = temp; }
// end of insert
if (StrExp.length()==1){StrExp = null;}
else
{
StrExp=StrExp.substring(1);
firstChar = StrExp.charAt(0);
}
break;
default:break;
}//end of switch statement
}//end of the bigger loop
} // end of GetTokens
// method to print tokens
public void printTokens ()
{
NodePtr temp = top;
while (temp != null)
{ System.out.println (temp.tokenPair.token +
" " + temp.tokenPair.type);
temp = temp.next;}
} // end of print
public static void main(String[] args)
{
Tokenizer a = new Tokenizer();
a.GetTokens();
a.printTokens();
} // end of main
}// end of class
Appendix B
/********************************************************************
S. Pham
11/11/99
Comp 110
Problem: #6
Status: Finished.
********************************************************************/
import java.io.*;
import java.lang.*;
import java.util.*;
import Tokenizer.*;
import NodePtr.*;
/*
class NodePtr
{
// Attributes of any member of NodePtr
TokenAndType tokenPair;
NodePtr next;
// Constructor to insert the node at the top of inputNodePtr
public NodePtr(TokenAndType tokenPair, NodePtr next)
{
this.tokenPair = tokenPair;
this.next = next;
}
public NodePtr()
{
tokenPair = new TokenAndType();
next = null;
}
public NodePtr( String tokenName,int tokenType)
{
tokenPair = new TokenAndType(tokenName, tokenType);
next = null;
}
}
*/
class LinkedListStacks
{
// Components
NodePtr top=null;
// the method push
public void push(TokenAndType inputToken)
{
top = new NodePtr(inputToken,top);
}
public NodePtr pop()
{
NodePtr popped = new NodePtr();
if (top == null)
{ System.out.println("stack is empty, unable to pop.");}
else
{ popped = top;
top = top.next;
}
return popped;
}
public void dump()
{ if (top == null)
{ System.out.println("Stack is empty" ); }
else
{
NodePtr temp = top;
while (temp != null)
{
temp.tokenPair.printTokenPair();
temp = temp.next;
}
}
}
}
class StackCaller2
{
public static void main(String[] args)
{
System.out.println("");
System.out.print("Initial Stacks:");
LinkedListStacks a = new LinkedListStacks();
a.dump();
System.out.println("");
System.out.print("Stacks after a push:");
TokenAndType t = new TokenAndType("2345", 5);
a.push(t);
a.dump();
System.out.println("");
System.out.print("Stacks after a pop:");
System.out.print("popped pair:" );a.pop().tokenPair.printTokenPair();
}
}