Implementation of stack

Question

Task:

Create a class RPNStack which represents a stack of objects of type Node. Class RPNStack contains only one private field top of type Node. Objects of type Node represent data that are pushed on the stack: each object contains in its field val a double and in field next a reference to the next node (as in a singly-linked list - top plays here the role of the head ). Class RPNStack offers three methods:

• method public void push(double d) pushing new object of type Node on top of the stack (i.e., it becomes the new top);
• method public double pop() removing the top node (so the next node becomes the new top) and returning val from the removed node;
• method public boolean empty() returning true if and only if the stack is empty (top is null); otherwise false is returned.

Note that stack is a singly-linked list where adding and removing elements is always performed at the beginning.

The main program reads a le with data representing arithmetic expressions in the Reverse Polish Notation (RPN), for example:

2 7 5 + * 20 - 1 4 / /

After reading each line, it is split (using spaces as separators) and for each token:

• if it is string "+", we pop two numbers from the stack, add them and push the result on the stack;
• if it is string "*", we do the same but myltiplying the numbers instead of adding them;
• if it is string "-", we pop two elements, subtract the one popped as the first from the one popped as the second and push the result on the stack;
• if it is string "/", we do the same but dividing the numbers instead of subtracting them;
• if it is not "+", "*", "-" or "/", we interpret it as a number of type double and we push it onto the stack.

After all tokens from the line have been processed, we pop the remaining number o the stack, which should be the value of the whole expression. We then print the line and the result. We also check if the stack is now empty; if not, we inform the user about this fact, we clear the stack and repeat the procedure for the remaining lines of the input file.

---

My Implementation:

I sligtly modify program to write to the file just to practice

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Path;
import java.nio.file.Paths;

public class Main {
    public static void main(String[] args) {
        String fileName = "Numbers.txt";
        String fileRes = "NumbersCalc.txt";
        Path filein = Paths.get(fileName);
        if (!Files.exists(filein)     ||
            !Files.isReadable(filein) ||
             Files.isDirectory(filein)) {
            System.out.println("Invalid input file !!!");
            System.exit(1);
        }
        try (BufferedWriter bw =
                Files.newBufferedWriter(Paths.get(fileRes));
             BufferedReader br =
                Files.newBufferedReader(filein)
            ) {
            String line;
            while ( (line = br.readLine()) != null) {
                String[] lineParts = line.split("\\s+");
                for (String string : lineParts) {
                    if(string.equals("+")){
                        RPNStack.push( RPNStack.pop() + RPNStack.pop() );
                    }else if(string.equals("-")){
                        RPNStack.push( RPNStack.pop() - RPNStack.pop() );
                    }else if(string.equals("*")){
                        RPNStack.push( RPNStack.pop() * RPNStack.pop() );
                    }else if(string.equals("/")){
                        RPNStack.push( RPNStack.pop() / RPNStack.pop() );
                    }else if(!string.equals("+") &&!string.equals("-")&&!string.equals("*")&&!string.equals("/")){
                        RPNStack.push(Double.parseDouble(string));
                    }
                }
                bw.write(RPNStack.pop()+System.lineSeparator()/*"\n"*/);
            }
            System.out.println("Results written to " + fileRes);
            if(RPNStack.empty()) System.out.println("Stack is empty");
        } catch(IOException e) {
            System.out.println("Something wrong");
            System.exit(1);
        }
    }
}


public class RPNStack {
    private static Node top = null;

    public static Node getTop() {
        return top;
    }
    public static void push(double d){
        if(top == null) top = new Node(d);
        else            top = new Node(d, top);
    }
    public static double pop(){
        double buf = top.getVal(); 
        top = top.getNext();
        return buf; 
    }
    public static boolean empty(){
        if(top == null) return true;
        else            return false;
    }
}

public class Node {
    private double val;
    private Node next;

    public double getVal() {
        return val;
    }
    public Node getNext() {
        return next;
    }

    public Node(double val, Node next){
        this.val=val;
        this.next=next;
    }
    public Node(double val){
        this(val,null);
    }
}

Numbers.txt:

2 7 5 + * 20 - 1 4 / /
2 7 5 + * 20 - 1 4 / /

Questions:

• I assume that we need to use static function in class RPNStack. Is it right?
• When I use BuffedWriter "\n" simply doesn't work(I expect print values from new line but its go one by one) so I have to use "System.lineSeparator()" and I don't understend why is that? Runing on Win 8.1\Eclipce Mars
• Is there a better way to recognise symbols than bunch on if else statements?
• Is it okay to use in try\catch only IOException? Or we need to use one more catch for Exception?
• What else can be done better?

Answer 1

Static methods on RPNStack

It is odd to write a class like RPNStack with all static methods and fields; effectively, you have a single global stack, for no particularly good reason.

The obvious thing to do would be to make all of those methods and fields instance methods/fields, and then create an instance of RPNStack within main().

Output

It isn't clear to me why "\n" would not be working for you where System.lineSeparator() does; however, you aren't closing or flushing the file, and it may be the case that some subtle difference is causing the file to be flushed in one case and not in the other.

I would expect that if you close your BufferedWriter at the end of your program, it will work fine.

Recognising symbols

The obvious and lightweight way to recognise a small set of symbols like this would be to use a switch statement. If you have Java 7+ (which you really should) you can just use strings directly as case labels; otherwise, you'd have to switch on characters (which would still work for your simple language). For a more complex language, you could consider a map from symbols to actions.

Error

There are kinds of errors which won't be caught by your catch (IOException). But I don't think you need to worry too much about those.

The only bit of error handling I would consider adding is that it's possible for the user to enter an expression which causes a divide by zero error. As your program stands, this will throw an ArithmeticException and terminate the program. I would suggest either catching the ArithmeticException and recovering with an error message, or validating the operands you're passing to the division operator.

Minor nitpicking

• Conventionally, you would print error messages to System.err rather than System.out.

• The RPNStack.empty() method could be more clearly written by just directly returning the value of the boolean expression:

  public boolean empty() { return top == null; }

• You don't need a special case for the first node on a stack: if you just do

  top = new Node(d, top);

  that will have the correct behaviour whether top points to a Node or is null.

• Consider checking whether the stack is empty when popping it; this will let you print a useful error message rather than dying with a null pointer exception.

Answer 2

if (!Files.exists(filein)     ||
     !Files.isReadable(filein) ||
     Files.isDirectory(filein)) {
     System.out.println("Invalid input file !!!");
     System.exit(1);
}

• Let's suppose that you see on your output the message Invalid input file !!! which of these three failed? Can you tell without going and manually checking? Food for thought.
• The three conditions together can be taken out into a separate methods with a meaningful name. Like

example

boolean isFileReadable(File file) 

Please replace the series of ifs with switch statement. It would be more readable.

String result = "";
String first = RPNStack.pop();
String second = RPNStack.pop(); 
switch(string) {
    case "+":
        result = first + second;
        break;
    //similarly all others. The last else if will become default:
 }
 RPNStack.push(result);

This way the logic is clear.

The reason why \n does not work on Windows is because different operating systems have different line separators. A quick google search can tell you what that means.

The assumption that the methods should be static will cause you to have a single Stack. You don't want that. static means belonging to class but what if you wanted to have two stacks in your program? You should have instance methods.

About this

System.out.println("Something wrong");

What's wrong? Where? If you catch an exception then you at least add the stacktrace to the printed messages. How? Google search.

About catching only IOException I say only catch what needs to be caught. If you are catching exceptions then if you can add some thing in the catch block to recover. If not possible then at least log a error message which does not require you to manually check what went wrong.

Now what else can be done better? You can use Java's generics to make your Stack reusable. You should have created a Stack class and then a RPNStack which used the generic stack class to do its stuff. In your example the thing that you are calling Main is actually the RPNStack as per the logic and the class that you have named RPNStack is a stack. The main class should have just given RPNStack the string and gotten the result out.