-2
\$\begingroup\$

Write a stack class from scratch to house integers using any programming language of your choosing that implements the following methods:

push(integer n) // adds the integer to top of the stack
pop()           // removes the top-most item from the stack
peek()          // gets the integer from top of the stack without removing it
depth()         // determines the number of integers in the stack

Use this stack class in a program that reads in a line of tokens, processes it, and outputs the results.

Do NOT use a pre-existing stack classes provided by a particular language, library, package, or framework. Your solution must contain your own implementation of a Stack class using best object-oriented programming practices.

Input Format

A single line of text containing tokens separated by spaces. A token can be any integer, the minus character (-), the question mark character (?), or the hash character (#), separated by spaces. Each token has the following meaning:

  • If a number, then the number is pushed onto the stack
  • If the minus character (-), a pop operation is performed against the stack
  • If the question mark character (?), a peek operation is performed
  • If the hash character (#), a depth operation is performed

Constraints

  • Inputs will not cause the stack to underflow
  • The stack must support depth d, where d < 2,000,000 without overflowing
  • -1048576000000 < n < 1048576000000
  • Using a pre-existing stack class provided by the programming language, library, package, or framework is not acceptable

Output Format

There shall be one line of output for each token in the input, per the following:

  • For an integer token, output the depth of the stack after the push operation
  • For a minus character (-), output the integer popped from the stack
  • For a question mark character (?), output the element peeked from the stack
  • For a hash character (#), output the depth of the stack

Sample Input

34 25 ? -5 - # ?

Sample Output

0 1 2 25 3
-5 2 25

Explanation

  • Before any integer is pushed onto the stack, the stack is empty, and therefore has zero elements. Per the input format specification, and "0" should be printed.
  • When token 34 is encountered, it is pushed onto the stack since it is an integer. Now stack has one element, and "1" should be printed.
  • When token 25 is encountered, it is pushed onto the stack as well. Stack now has two elements, and "2" should be printed.
  • When token ? is encountered, it peeks at the stack, and prints "25" since that is the top-most element in the stack.
  • When token -5 is encountered, it is pushed onto the stack and "3" is printed.
  • When token - is encountered, the top-most element is popped from the stack, and "-5" is printed
  • When token # is encountered, "2" is printed because the stack now has two elements.
  • When token ? is encountered, "25" is printed because it is at the top of the stack.

This is how I implemented it:

import java.io.*;
import java.util.*;
import java.lang.*;

public class StackThemUp {
  private static LinkedList<Long> list = new LinkedList<>();


  @SuppressWarnings("resource")
  public static void main(String[] args) {

    int stackSize;
    long lastInt;
    String line = "";
    try (BufferedReader reader = new BufferedReader(new InputStreamReader(System.in))) {     
    line = reader.readLine();
} catch (IOException exc) {
}
for (String s : line.split(" ")) {
  try {
    if (s.equals("?")) {
        lastInt = peek();
        System.out.println(lastInt);
    } else if (s.equals("#")) {
        if(list.size()>0){ 
        stackSize = depth();
        System.out.println(stackSize);
        }
    } else if (s.equals("-")) {
       if(list.size()>0){
       lastInt = peek();
       System.out.println(lastInt);
       pop();
       }
    } else if (s.matches("[-]?\\d+")) {
        push(Long.parseLong(s));
        stackSize = depth();
        System.out.println(stackSize);
    } else {
      throw new IllegalArgumentException();
    }
  } catch (IllegalArgumentException ex) {
    }
 }
}
  private static void push(Long number) {
  list.add(number);
  }

  private static Long peek() {
  return list.getLast();
  }

  private static int depth() {
  return list.size();
  }

  private static void pop() {
  if (list.size() > 0)
  list.removeLast();
  }
}

This passes every test except for one where it times out. I had tried to solve it without regex (used :

private static boolean validateInteger(String text) {
  try {
    Long.parseLong(text);
    return true;
  } catch (NumberFormatException ex) {
    return false;
  }
}

......but still it failed the timed-out test case.

\$\endgroup\$
  • 1
    \$\begingroup\$ Please add more information on the problem you are trying to solve. Also, please format your code properly with the correct indentation. \$\endgroup\$ – JS1 Feb 22 '17 at 1:51
  • \$\begingroup\$ hope it helps now... \$\endgroup\$ – codeToEnlight Feb 22 '17 at 4:08
  • 2
    \$\begingroup\$ What test case does it fail? And is timing out the only problem or are there actually bugs in your program? Why did you pick regex to solve your problem? That hardly seems in line with the spirit of the question. \$\endgroup\$ – Mast Feb 22 '17 at 7:36
  • \$\begingroup\$ It only fails the timed-out test case. I had tried to solve it without regex(used : private static boolean validateInteger(String text) { try { Long.parseLong(text); return true; } catch (NumberFormatException ex) { return false; } } ) ......but still it failed the timed-out test case. \$\endgroup\$ – codeToEnlight Feb 22 '17 at 13:15
1
\$\begingroup\$
  private static LinkedList<Long> list = new LinkedList<>();

A LinkedList implements a Deque interface, which supports Stack operations. It may fail the "from scratch" requirement. If I were doing this, I would likely use an array.

  private static long[] stack = new long[2000000];
  int size = 0;

Since you're guaranteed a maximum depth of 2,000,000, you can go ahead and allocate that much memory immediately. You're virtually guaranteed to need that much memory for at least one test case.

  private static void push(Long number) {
  list.add(number);
  }

  private static Long peek() {
  return list.getLast();
  }

  private static int depth() {
  return list.size();
  }

  private static void pop() {
  if (list.size() > 0)
  list.removeLast();
  }

With an array

  private static void push(long number) {
    stack[size] = number;
    size++;
  }

  private static long peek() {
    return stack[size - 1];
  }

  private static int depth() {
    return size;
  }

  private static void pop() {
    if (size > 0) {
      size--;
    }
  }

As we don't know why your code was timing out, we don't know if this will fix it. It might. A linked list is a poor data structure for doing lots of inserts, as it has to keep allocating memory. This code allocates memory just once.

Note that they don't promise not to overflow the stack, just not to underflow it. Maybe the timeout is that they are waiting for you to reject a stack overflow. Absent more detail, it's all just speculation.

  try {
    if (s.equals("?")) {
        lastInt = peek();
        System.out.println(lastInt);
    } else if (s.equals("#")) {
        if(list.size()>0){ 
        stackSize = depth();
        System.out.println(stackSize);
        }
    } else if (s.equals("-")) {
       if(list.size()>0){
       lastInt = peek();
       System.out.println(lastInt);
       pop();
       }
    } else if (s.matches("[-]?\\d+")) {
        push(Long.parseLong(s));
        stackSize = depth();
        System.out.println(stackSize);
    } else {
      throw new IllegalArgumentException();
    }
  } catch (IllegalArgumentException ex) {
    }
 }

Two things. First, I'd use a switch.

if (str.length() == 1) {
  switch (s.charAt(0)) {
    case '?':
      System.out.println(peek());
      break;
    case '#':
      System.out.println(depth());
      break;
    case '-':
      if (size > 0) {
        System.out.println(peek());
        pop();
      }
      break;
    default:
      push(Long.parseLong(s));
      System.out.println(depth());
  }
} else {
  push(Long.parseLong(s));
  System.out.println(depth());
}

Second, I wouldn't throw an exception inside a try to be caught without effect. Just skip it.

You also might leave off the size > 0 check, since they promise to never do that. You don't check it on peek, which has the same problem.

You could catch just the NumberFormatException rather than the more general IllegalArgumentException, but I doubt it matters.

\$\endgroup\$
  • \$\begingroup\$ I tried with all the changes you suggested, but still out of luck. \$\endgroup\$ – codeToEnlight Feb 23 '17 at 0:26
  • \$\begingroup\$ But Good points though...appreciate that. \$\endgroup\$ – codeToEnlight Feb 23 '17 at 0:32
  • \$\begingroup\$ BTW how do I reject the overflow? \$\endgroup\$ – codeToEnlight Feb 23 '17 at 0:36
  • \$\begingroup\$ I tried to reject the overflow like this: private static void push(long number) { if(size<=2000000){ stack[size] = number; size++; } } //but dint solve the issue either. \$\endgroup\$ – codeToEnlight Feb 23 '17 at 0:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.