1

I have an input file ("student.json") that consists of a few lines of JSON code such as: 

{"name":"Josh","age":22,"gender":"M"}

that will be used in a Java program. The program should input the file, grab a JSON string, and then use a character stack to validate the syntax (the program should ignore what the specific property [name] and value [Josh] is, but know that each set of braces MUST have at least 2 values with a colon between). If the syntax is correct the console will tell the user that the JSON string is valid, if it is not valid the console will say so.

For the character stack I am to loop through each character of the JSON string. When an opening brace or bracket is encountered the program should push it on the stack. When a closing brace or bracket is encountered the program should then pop a value off the stack and see if it matches. I am also supposed to use the isEmpty method to see if there are unmatched symbols.

I have never used a character stack before. I know how to do the rest of the Java program, it is just the stack I am stuck on.

Question: How do I validate the JSON string using this character stack and the requirements?

Improve this question
5
  • 1
    It seems you already have a good idea on how to solve the problem: when there is an opening character, you add it to the stack. When there is a closing character, you pop the stack (so you get the last character added) and you check that it is the corresponding closing character. What do you need exactly? Code? Details on how a stack works? Commented Jan 12, 2015 at 21:41
  • @VincentDurmont A coded example would work for me. I have never worked with stacks before, so I am not sure what the syntax is for popping values, etc., and my Java book is utterly useless. Commented Jan 12, 2015 at 21:45
  • You'll need to model a stack machine. It will need to have at least two states: “inside quoted string” and “outside of quoted string”. You can use a Deque<Character> for your stack. But please don't expect that we will provide you with a complete solution here. It is your homework, after all. Commented Jan 12, 2015 at 21:48
  • @5gon12eder Of course. I don't expect anyone to write a complete solution. I just need an example of how to implement a character stack and how to pop values, etc., as I have never used one before and my book does not cover stacks. Commented Jan 12, 2015 at 22:05
  • I assume this is a class assignment. Otherwise the very strong recommendation would be to use one of the two dozen or so available JSON parsers to read your JSON source. As to the character stack, it's basically a poor-man's recursion -- used to "remember" the current state when you "push" a new state due to encountering, say, a { character indicating the start of a new JSON object. Commented Jan 12, 2015 at 22:25

2 Answers 2

Reset to default
1

A stack is basically this interface:

public interface Stack<T> {
    void push(T item); // adds an item to the stack
    T peek(); // looks what is the last item in the stack
    T pop(); // removes and returns the last item of the stack
    boolean isEmpty(); // are there items in the stack?
}

It's not pretty code but here is an example to solve your problem (using the built-in java.util.Stack class):

public static boolean isValid(String str) {
    Stack<Character> stack = new Stack<>();
    for (char c : str.toCharArray()) {
        switch (c) {
            case '{':
                stack.push(c);
                break;
            case '}':
                if (stack.isEmpty()) {
                    return false;
                }
                Character last1 = stack.pop();
                if (last1 != '{') {
                    return false;
                }
                break;
            case '\"':
                if (stack.isEmpty()) {
                    return false;
                }
                Character last2 = stack.peek();
                if (last2 == '\"') {
                    // It's a closing quote
                    stack.pop();
                } else {
                    // It's an opening quote
                    stack.push(c);
                }
                break;
        }
    }
    return stack.isEmpty();
}

With tests:

@Test public void isValid_if_true() {
    String jsonString = "{\"name\": \"John\"}";
    assertTrue(JsonValidator.isValid(jsonString));
}

@Test public void isValid_if_too_many_opened_brackets() {
    String jsonString = "{\"name\": \"John\", {}";
    assertFalse(JsonValidator.isValid(jsonString));
}

@Test public void isValid_if_too_many_closed_brackets() {
    String jsonString = "{\"name\": \"John\", }}";
    assertFalse(JsonValidator.isValid(jsonString));
}

@Test public void isValid_if_too_many_quotes() {
    String jsonString = "{\"name\": \"\"John\"}";
    assertFalse(JsonValidator.isValid(jsonString));
}

You will still have to check that you have at least 2 properties in your JSON object and to verify the position of the ,.

Try to play the algorithm on paper to see how it works.

Basically we ignore all the characters except the brackets and the quotes. When we get one of those special characters, we check if they are opening a new "token" (push to stack), closing one (pop from stack) or if there is a problem.

I hope it helps.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Thanks! I was able to figure out the rest based on your example. +1
0

Is it absolutely a requirement to validate by manually parsing the JSON? If it isn't, I would suggest using Jackson's ObjectMapper: http://fasterxml.github.io/jackson-databind/javadoc/2.2.0/com/fasterxml/jackson/databind/ObjectMapper.html#readTree(java.lang.String)

If you are trying to do it manually you will have to worry about nested objects and arrays.

EDIT:

Stacks

I assume you know the basics of what a stack is (LIFO) but you are interested in learning how the are implemented underneath the hood. If you are able to, use a Java LinkedList as the underlying data structure. It will be harder if you have to use a simple array because you will have to handle resizing and therefore moving all elements of the array around.

Using a LinkedList, you simply add(E)/addFirst(E) for every push to the stack and then getLast()/getFirst() for every pop.

You can find an example in this post: Stack array using pop() and push()

Improve this answer

5 Comments

Unfortunately it is necessary to achieve this manually, though I do not need to worry about nested objects or arrays, thankfully.
Ok so I now understand that this is for class. How manual does this process need to be? Are you able to use Java's standard String functionality? Are you able to use a stack that you didn't write?
I can use the standard String functionality, but I can't use a stack I didn't write.
Honestly, the easiest way (assuming that this doesn't break the rules of the assignment) is to loop through the String and count the number of braces and quotes. There should be a closing brace for every opening brace and an even number of quotes. There should be whitespace or a quote after every opening brace, colon, and comma (unless the value after a colon is a number). You could improve this further by using simple regular expressions.
However, I assume that does not follow the guidelines of the assignment. It does indeed appear that you have a good idea about the algorithm for validating the JSON. I will update my original answer with information about stacks.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.