4 Replies Latest reply: Oct 9, 2012 12:40 PM by EJP RSS

    In your lab05, replace instructor’s Tokenizer class and MyStackQueue packag

    967152
      Objective:

      The objective of this lab is to get you some experience in processing strings character by
      character and in implementing stacks and queues in a class package.

      The programming assignment:
      In your lab05, replace instructor’s Tokenizer class and MyStackQueue package with your own.

      Requirements:
      1. You must use an array to implement your queue.
      2. You must use a linked list to implement your stack.
      3. You must use the following frame work to implement your tokenizer.
      class Tokenizer {
      private char [] Buf;
      private int cur;
      Tokenizer(String infixExpression) {
      Buf = infixExpression.toCharArray();
      cur = 0;
      }
      Token nextToken() {
      1. Skip blanks.

      2. if (cur>=Buf.length) return null;

      3. If the next character is a digit, keep reading until a non-digit is read.

      Convert the string of digits into an integer.
      String Digits = new String(Buf, start, len);
      int num = Integer.valueOf(Digits).intValue();
      Create and return an operand.
      4. Otherwise, use the next character to create and return an operator.
      }
      }


      class Tokenizer {
           private char[] Buf;
           private int cur;

           Tokenizer(String infixExpression) {
                Buf = infixExpression.toCharArray();
                cur = 0;
           }

           Token nextToken() {
                int bufLength = Buf.length;
                Object obj = null;
                // ignore blank space
                while (cur < bufLength && Buf[cur] == ' ') {
                     cur++;
                }

                // if given string having only space return null
                if (cur >= Buf.length)
                     return null;

                StringBuilder value = new StringBuilder();
                // Iterate through each element of string array and construct an string
                // for consecutive digits
                while (cur < bufLength && Buf[cur] <= '9' && Buf[cur] >= '0') {
                     value.append(Buf[cur]);
                     cur++;
                }
                // if digits are there convert all digits as an integer value and create
                // operand
                if (value.length() > 0) {
                     obj = new Operand(Integer.parseInt(value.toString()));
                }
                // if at cur position no digit is present then create operand with the
                // same non digit value
                else {
                     obj = new Operator(Buf[cur]);
                     cur++;
                }
                return ((Token) (obj));
           }

      }


      package StackAndQueue;

      public class Queue {

           private int front;
           private int rear;
           private int capacity;
           private Object S[];

           public Queue() {
                front = 0;
                rear = -1;
                capacity = 100;
                S = new Object[capacity];
           }

           public boolean isEmpty() {
                return S[front] == null;
           }

           public void enqueue(Object obj) {
                int insertionPoint = (rear + 1) % capacity;
                if (S[insertionPoint] == null) {
                     S[insertionPoint] = obj;
                     rear = insertionPoint;
                } else {
                     System.out.println("Queue capacity is full");
                }
           }

           public Object dequeue() {
                if (S[front] != null) {
                     Object obj = S[front];
                     S[front] = null;
                     front = (front + 1) % capacity;
                     return obj;
                } else {
                     System.out.println("Queue is empty");
                     return null;
                }
           }

           public String toString() {
                StringBuilder state = new StringBuilder("[");
                for (int i = front; i < capacity; i++) {
                     if (S[i] != null) {
                          state.append(S[i] + ", ");
                     }
                }
                for (int i = 0; i < front; i++) {
                     if (S[i] != null) {
                          state.append(S[i] + ", ");
                     }
                }
                if (state.length() > 1) {
                     state.delete(state.length() - 2, state.length() - 1);
                }
                state.append("]");
                return state.toString();
           }
      }

      package StackAndQueue;

      import java.util.LinkedList;
      import java.util.List;

      public class Stack {

           List<Object> linkedList = null;

           public Stack() {
                linkedList = new LinkedList<Object>();
           }

           public boolean isEmpty() {
                return linkedList.size() == 0;
           }

           public void push(Object obj) {
                linkedList.add(obj);
           }

           public Object pop() {
                int topIndex = linkedList.size() - 1;
                if (topIndex >= 0) {
                     Object obj = linkedList.get(topIndex);
                     linkedList.remove(topIndex);
                     return obj;
                } else {
                     return null;
                }
           }

           public Object top() {
                int topIndex = linkedList.size() - 1;
                if (topIndex >= 0) {
                     return linkedList.get(topIndex);
                } else {
                     return null;
                }
           }
      }