Google Interview Question
Country: India
Approach:
We can use recursion to solve this question
bool checkJason(string str, int &index){}
step1: when you hit character '{', call recursion . And recursion function returns boolean value.
Step2: valid Json string must have equal number of open and closed brackets '{' & '}'
step3: when we hit delimiter characters ',', '{','}' call checkJasonValuePair(string str, bool allowSuffixColon=false)
step4: CheckJsonValuePair() validate whther the string has ':' character or not.
bool checkJasonValuePair(string str, bool allowSuffixColon=false)
{
if (str.empty())
return true;
int colCount = 0;
for (int i = 0; i< str.length(); i++)
{
if (str[i] == ':')
colCount++;
}
// suffix sould not be :
if (!allowSuffixColon && str[str.length() - 1] == ':')
return false;
return colCount == 1 ? true : false;
}
bool checkJason(string str, int &index)
{
if (str.empty())
{
return true;
}
stack<char> stk;
int i = index;
while (i < str.length())
{
if (str[i] == '{')
{
stk.push('{');
string temp;
i++;
while (i < str.length() && str[i] != ',' && str[i] != '}' && str[i] != '{')
{
temp += str[i];
i++;
}
if (i == str.length() || !checkJasonValuePair(temp, str[i] == '{'))
return false;
if (str[i] == '{' && !checkJason(str, i)) // recursive functrion
return false;
}
else if (str[i] == ',')
{
i++;
string temp;
while (i < str.length() && str[i] != '}' && str[i] != ',' && str[i] != '{')
{
temp += str[i];
i++;
}
if (i == str.length() || !checkJasonValuePair(temp, str[i] == '{'))
return false; // last charcter should be ‘}’
else if (str[i] == '{' && !checkJason(str, i)) // recursive functrion
return false;
}
else
{
if (str[i] == '}')
{
if (stk.empty() || stk.top() != '{')
return false;
stk.pop();
}
i++;
return true;
}
}
return stk.empty() ? true: false;
}
int main()
{
int index = 0;
cout << " Valid Jason {} = " << checkJason("{}", index) << endl;
index = 0;
cout << " Valid Jason {a}= " << checkJason("{a}", index) << endl; // false
index = 0;
cout << " Valid Jason {a:b}= " << checkJason("{a:b}", index) << endl;
index = 0;
cout << " Valid Jason {a:{b:c}}= " << checkJason("{a:{b:c}}", index) << endl;
index = 0;
cout << " Valid Jason {a:b, c:d} = " << checkJason("{a:b, c:d}", index) << endl;
index = 0;
cout << " Valid Jason {a:b, c{:d}} = " << checkJason("{a:b, c{:d}}", index) << endl;//false
index = 0;
cout << " Valid Jason {a:} = " << checkJason("{a:}", index) << endl;//false
getchar();
}
bool JSONValidation(string json)
{
size_t keyCount = 0, valueCount = 0, leftBraceCount = 0, rightBraceCount = 0;
ostringstream oss;
string key = "", value = "";
for (string::const_iterator it = json.begin(); it != json.end(); it++)
{
if (*it == '{')
{
leftBraceCount++;
key = "";
value = "";
oss.str("");
}
else if (*it == '}' || *it == ' ' || *it == ',') {
value = oss.str();
oss.str("");
if (value != "")
valueCount++;
if (*it == '}')
rightBraceCount++;
if (leftBraceCount > rightBraceCount && keyCount > valueCount)
valueCount++;
}
else if (*it == ':') {
key = oss.str();
oss.str("");
if (key != "")
keyCount++;
}
else
oss << *it;
}
return leftBraceCount == rightBraceCount && keyCount == valueCount;
}
/\A("([^"\\]*|\\["\\bfnrt\/]|\\u[0-9a-f]{4})*"|-?(?=[1-9]|0(?!\d))\d+(\.\d+)?([eE][+-]?\d+)?|true|false|null|\[(?:(?1)(?:,(?1))*)?\s*\]|\{(?:\s*"([^"\\]*|\\["\\bfnrt\/]|\\u[0-9a-f]{4})*"\s*:(?1)(?:,\s*"([^"\\]*|\\["\\bfnrt\/]|\\u[0-9a-f]{4})*"\s*:(?1))*)?\s*\})\Z/
Regular expression to validate a json.
import java.util.*;
public class Solution {
public boolean checkJson(String S, int start, int end){
if(start == end ) return false;
int idx = start;
if(S.charAt(idx) != '{')
return false;
int i = start+1;
while(true){
//verify key
while(i <= end){
if(S.charAt(i) >= 'a' && S.charAt(i) <= 'z') i++;
else if(S.charAt(i) == ':')break;
else return false;
}
if(i==start+1 || i >= end) return false;
if(S.charAt(i) != ':')return false;
//verify value
++i;
if(i > end) return false;
if(S.charAt(i) == '{'){ //value is new json get this and test
boolean res = false;
int tempStart = i+1 ;
int count = 1;
while(count > 0 && tempStart <= end){
if(S.charAt(tempStart) =='{') ++count ;
else if(S.charAt(tempStart) =='}') --count ;
++tempStart;
}
if(tempStart > end) return false;
res = checkJson(S,i,tempStart-1);
i = tempStart;
if(!res) return false;
}
else{
int j = i ;
while(j <= end){
if(S.charAt(j) >= 'a' && S.charAt(j) <= 'z') j++;
else break;
}
if(j == i ) return false;
i = j;
}
if(S.charAt(i) == ','){++i; continue;}
else break;
}
if(S.charAt(i) == '}' && i == end) return true;
return false;
}
public static void main(String[]s){
Solution ob = new Solution();
String S = "{a:b,c:{d:f}";
System.out.println(S+" "+ob.checkJson(S,0,S.length()-1));
}
}
{{
public static void main(String[] args) {
// TODO Auto-generated method stub
System.err.println(isValidJson("{a:b}"));
System.err.println(isValidJson("{a:b, c:d}"));
System.err.println(isValidJson("{a:b,c:{e:f}}"));
System.err.println(isValidJson("{{a}}"));
}
private static boolean isValidJson(String string) {
//Split by ',' first. Then go through each
//Use Stack . If a } is encountered , pop each element from stack
Stack<String> stack = new Stack<String>();
int ilen = string.length();
for(int i = 0 ; i < ilen; ++i) {
char c = string.charAt(i);
if ( c=='{') {
stack.push(String.valueOf(c));
} else if (c==',') {
if(!validateComma(stack))
return false;
}else if ( c== '}'){
if(!validateBraces(stack))
return false;
} else {
stack.push(String.valueOf(c));
}
}
return true;
}
private static boolean validateBraces(Stack<String> stack) {
String jsonTemp = new String();
boolean flag = true;
while(flag) {
String temp = stack.pop();
if(temp.equals("{")) {
//Validate temp as valid
String[] tempA = jsonTemp.split(":");
if (tempA.length != 2)
return false;
else
return true;
}
jsonTemp = jsonTemp + temp;
}
return false;
}
private static boolean validateComma(Stack<String> stack) {
//Means a new json string found. So extract each value till { is encontered
String jsonTemp = new String();
boolean flag = true;
while(flag) {
String temp = stack.pop();
if(temp.equals("{")) {
flag = false;
stack.push("{");
//Validate temp as valid
String[] tempA = jsonTemp.split(":");
if (tempA.length != 2)
{
return false;
} else {
return true;
}
}
jsonTemp = jsonTemp + temp;
}
return false;
}
}}
I think you only need to track the commas.
1. Trim the spaces
2. Verify that the JSON starts/ends with curly braces
3. Every time you see a comma, check the string you've just built to see if it's a valid key/value pair
4. If it had curly braces in the value, then you'll be recursively calling the main validate function on that substring.
import java.util.*;
public class ValJSON {
public static void main( String args[] ) {
ValJSON vj = new ValJSON();
if( vj.validJSON( args[0] )) {
System.out.println( "Valid" );
} else {
System.out.println( "Not Valid" );
} // end if/else
} // end main
public boolean validJSON( String json ) {
json = json.trim();
StringBuilder sb = new StringBuilder();
String beforeColon = new String();
if( json.charAt( 0 ) != '{' || json.charAt( json.length() - 1 ) != '}' ) return false;
for( int i = 1; i < json.length() - 1; i++ ) {
char c = json.charAt( i );
if( c == ',' ) {
valComma( sb.toString());
sb = new StringBuilder();
} else {
if( c == '{' && ( sb.length() <= 0 || sb.charAt( sb.length() - 1 ) != ':' )) return false;
sb.append( String.valueOf( c ));
} // end if/else
} // end for
return valComma( sb.toString());
} // end validJSON
private boolean valComma( String json ) {
System.out.println( "Looking at: " + json );
if( json.length() < 1 ) return false;
int idx = json.indexOf( ":" );
if( idx == -1 || idx == json.length() - 1 ) {
return false;
} else {
if( json.charAt( idx + 1 ) == '{' ) {
return validJSON( json.substring( idx + 1 ));
} else {
return true;
} // end if/else
} // end if/else
} // end valComma
} // end ValJSON
public class JsonValid {
public boolean isValid(String s) {
//System.out.println("-" + s + "-");
if(s.trim().isEmpty()) return false;
if(s.length() == 1) {
//System.out.println("yes it's one length");
//System.out.println(Character.isLetter(s.charAt(0)));
return Character.isLetter(s.charAt(0));
}
if(s.charAt(0) == '{' && s.charAt( s.length()-1 ) == '}') {
String[] elements = s.substring(1,s.length()-1).split(",");
if(elements.length == 0) return false;
for(String element : elements) {
if(element.length() <= 2) {
return false;
}
//System.out.println(element + " " +element.substring(2,element.length()));
if( !Character.isLetter(element.charAt(0)) || element.charAt(1) != ':' ) return false;
if( !isValid(element.substring(2,element.length())) ) return false;
}
}else {
return false;
}
return true;
}
public static void main(String[] args) {
JsonValid jv = new JsonValid();
System.out.println(jv.isValid(""));
System.out.println(jv.isValid("a"));
System.out.println(jv.isValid("{a::}"));
System.out.println(jv.isValid("{a:b}"));
System.out.println(jv.isValid("{a}"));
System.out.println(jv.isValid("{{a}}"));
System.out.println(jv.isValid("{a:b,c:{e:f}}"));
}
}
One basic idea while parsing is that "all the elements in the left of current position has been validated properly." We are using the stack to check the validity of the given string. So, all the elements at same level which are present in the stack are already been validated.
Basic trim functions:
char* trim(char *str) {
while (*str == ' ')
str++;
return str;
}
char* trimRear(char *str) {
int len = str ? strlen(str) : 0;
for (int i = len-1; i >= 0; i--) {
if(str[i] == ' ')
str[i] = '\0';
else break;
}
return str;
}
Helper functions:
// Check whether there is only one ":" mark in the string or not.
int onlyTwoTokens(string str) {
size_t firstPos = str.find_first_of(":");
if (firstPos == string::npos)
return -1;
size_t rearPos = str.find_last_of(":");
if (firstPos == rearPos)
return 2;
return -1;
}
// Count total number of tokens in the given string
int countTokens(string str, char token) {
size_t pos = str.find(token);
int count = 0;
while (pos != string::npos) {
count ++;
pos = str.find(token, pos+1);
}
return count;
}
One basic notion, we should develop while solving this is that "a:b" is an object or entity. Here we use '-' marker to denote such objects.
bool checkObjects(stack<char> &s) {
if(s.empty())
return false;
bool result = false;
string str;
while (!s.empty() && !result) {
char ch = s.top();
s.pop();
if (ch == ',') { // we found a sibling in same level
if (onlyTwoTokens(str) != 2)
return false;
result = true; // All the elements are present in the same level and already been validated.
// We need not to push one ',' and a '-' here. Since the previous element will take care of it.
}
else if (ch == '{'){ // It is the first object in that level, we must have one ":"
if (onlyTwoTokens(str) != 2)
return false;
s.push('{');
s.push('-'); // This is our object marker, one object has been found at the very beginning
result = true;
}
str += ch;
}
return result;
}
bool checkForSiblings(stack<char> &s) {
if(s.empty())
return false;
string str;
bool result = false;
while (!s.empty() && !result) {
char ch = s.top();
s.pop();
if (ch == '{') {
// Total number of '-' should be once greater than ','
int countSeparator = countTokens(str, ',');
int countObjectMarkers = countTokens(str, '-');
if (countObjectMarkers == countSeparator && countObjectMarkers == 0)
result = true; // Empty object
else if (countObjectMarkers == countSeparator+1)
result = true; // All the object markers are separated by separators.
break;
}
else if (ch == ',') {
if (onlyTwoTokens(str) != 2)
return false;
str.clear(); // We need to flush it, as the separator and the object are matched. Rest be handled by previous object
continue;
}
str += ch;
}
return result;
}
Basic JSON validator code with basic error handling.
bool jsonValidator(char *str)
{
// Trim all the white spaces.
str = trim(str);
str = trimRear(str);
int len = 0;
// we need at most 2 characters to start with
if (str == NULL || (len = strlen(str)) < 2)
return false;
stack<char> s;
for (int i = 0; i < len; i++) {
switch(str[i]) {
case ' ': // skip whitespaces
if(s.empty())
return false;
break;
case ',': // handle ','
if (!checkObjects(s))
return false;
s.push(',');
break;
case '{':
if (!s.empty() && s.top() == '{') // Handle strings like this "{{"
return false;
s.push('{');
break; // handle open braces
case '}':
// It's a candiate for whole object at the same level
if(!checkForSiblings(s))
return false;
s.push('-'); // Denote as whole object
break; // handle close braces
default:
s.push(str[i]);
break;
}
}
// at the end all the elements of stack should be popped
return (s.size() == 1 && s.top() == '-');
}
public static bool IsValidJson(string json)
{
return RecIsValidJson(new StringBuilder(json));
}
private static Regex prop = new Regex(@"^(([a-z]|[A-Z])\w*):(([a-z]|[A-Z])\w*)$", RegexOptions.Compiled);
private static Regex obj = new Regex(@"^(([a-z]|[A-Z])\w*):\{.*\}", RegexOptions.Compiled);
private static bool RecIsValidJson(StringBuilder json)
{
if (!json.ToString().StartsWith("{") || !json.ToString().EndsWith("}"))
{
return false;
}
json.Remove(0, 1);
json.Remove(json.Length-1, 1);
string[] s = json.ToString().Split(new char[] {','});
foreach (var str in s)
{
if (prop.IsMatch(str))
{
continue;
}
if (obj.IsMatch(str))
{
int index = str.IndexOf(":");
if(!RecIsValidJson(new StringBuilder(str.Substring(index+1, str.Length - (index + 1)))))
{
return false;
}
}
else
{
return false;
}
}
return true;
}
We use simple grammar rules for JSON:
JSON -> {x}
x -> terminal:terminal
x -> terminal:JSON
x -> x,x
The code below assumes there are no white spaces in between and all the terminals are one character long. This was done to keep the code look simple.
public class IsValidJSON {
public static void main(String[] args)
{
System.out.println(IsStringValidJson("{a:b}"));
System.out.println(IsStringValidJson("{a:b,c:d}"));
System.out.println(IsStringValidJson("{a:b,c:{e:f}}"));
System.out.println(IsStringValidJson("{{a}}"));
}
// We form a simple grammer for the JSON:
// JSON -> {X}
// x -> terminal:terminal
// x -> terminal:JSON
// x -> x,x
private static boolean IsStringValidJson(String jsonString)
{
char[] jsonCharArray = jsonString.toCharArray();
if (jsonCharArray[0] != '{')
{
return false;
}
if (jsonCharArray[jsonCharArray.length-1] != '}')
{
return false;
}
return IsValidNonTerminal(jsonString.substring(1, jsonString.length()-1));
}
private static boolean IsValidNonTerminal(String jsonString)
{
if (jsonString == null || jsonString == "")
{
return false;
}
if (jsonString.indexOf(",") != -1)
{
// We have x->x,x
int indexOfComma = jsonString.indexOf(",");
return IsValidNonTerminal(jsonString.substring(0, indexOfComma)) &&
IsValidNonTerminal(jsonString.substring(indexOfComma+1));
}
else if (jsonString.indexOf("{") != -1)
{
// We have x->ter:JSON
int indexOfLeftBrace = jsonString.indexOf("{");
return IsValidTerminalWithColon(jsonString.substring(0, indexOfLeftBrace)) &&
IsStringValidJson(jsonString.substring(indexOfLeftBrace));
}
else
{
if (jsonString.length() != 3)
{
return false;
}
char[] charArray = jsonString.toCharArray();
if (!IsTerminal(charArray[0]) || !IsTerminal(charArray[2]))
{
return false;
}
if (charArray[1] != ':')
{
return false;
}
return true;
}
}
private static boolean IsValidTerminalWithColon(String jsonString)
{
char[] charArray = jsonString.toCharArray();
if (charArray.length != 2)
{
return false;
}
if (!IsTerminal(charArray[0]))
{
return false;
}
if (charArray[1] != ':')
{
return false;
}
return true;
}
private static boolean IsTerminal(char c)
{
if (c <= 'z' && c >= 'a')
{
return true;
}
return false;
}
}
This solution uses a DFA, I hope it helps someone.
package io.github.zimuzostanley.algo;
public class Json {
private static final char COLON = ':'; // 0
private static final char O_BRACE = '{'; // 1
private static final char C_BRACE = '}'; // 2
private static final char COMMA = ','; // 3
// Others is 4
private static final int COLON_REP = 0;
private static final int O_BRACE_REP = 1;
private static final int C_BRACE_REP = 2;
private static final int COMMA_REP = 3;
private static final int OTHERS_REP = 4;
private static final int STATE_KEY = 0;
private static final int STATE_COLON = 1;
private static final int STATE_VALUE = 2;
private static final int STATE_COMMA = 3;
private static final int STATE_O_BRACE = 4;
private static final int STATE_C_BRACE = 5;
private static int getRepresentaion(char ch) {
switch(ch) {
case COLON:
return COLON_REP;
case O_BRACE:
return O_BRACE_REP;
case C_BRACE:
return C_BRACE_REP;
case COMMA:
return COMMA_REP;
default:
return OTHERS_REP;
}
}
private static int[][] buildDfa() {
int[][] dfa = new int[6][5];
for (int i = 0; i < dfa.length; i++) {
for (int j = 0; j < dfa[0].length; j++) {
dfa[i][j] = -1;
}
}
dfa[STATE_KEY][COLON_REP] = STATE_COLON;
dfa[STATE_COLON][OTHERS_REP] = STATE_VALUE;
dfa[STATE_COLON][O_BRACE_REP] = STATE_O_BRACE;
dfa[STATE_VALUE][COMMA_REP] = STATE_COMMA;
dfa[STATE_VALUE][C_BRACE_REP] = STATE_C_BRACE;
dfa[STATE_COMMA][OTHERS_REP] = STATE_KEY;
dfa[STATE_C_BRACE][COMMA_REP] = STATE_COMMA;
dfa[STATE_C_BRACE][C_BRACE_REP] = STATE_C_BRACE;
dfa[STATE_O_BRACE][OTHERS_REP] = STATE_KEY;
dfa[STATE_O_BRACE][C_BRACE_REP] = STATE_C_BRACE;
return dfa;
}
private static int getNextState(int[][] dfa, int curState, char ch) {
int rep = getRepresentaion(ch);
return dfa[curState][rep];
}
private static boolean countOAndCBrace(String text) {
int ocount = 0;
int ccount = 0;
for (Character c: text.toCharArray()) {
if (c == O_BRACE) {
ocount++;
}
else if (c == C_BRACE) {
ccount++;
}
}
return ocount == ccount;
}
private static boolean checkInput(String input) {
if (!countOAndCBrace(input)) {
System.out.println("Mismatching braces");
return false;
}
if (input.charAt(0) != O_BRACE) {
System.out.println("O_Brace");
return false;
}
int[][] dfa = buildDfa();
int state = STATE_O_BRACE;
for (int i = 1; i < input.length(); i++) {
state = getNextState(dfa, state, input.charAt(i));
if (state == -1) {
System.out.println("Wrong state");
return false;
}
}
if (state == STATE_C_BRACE) {
return true;
}
System.out.println("End");
return false;
}
public static void main(String[] args) {
if (args.length != 1) {
System.out.println("Please enter a correct input");
return;
}
String input = args[0];
if (checkInput(input)) {
System.out.println("Valid");
}
else {
System.out.println("Invalid");
}
}
}
package io.github.zimuzostanley.algo;
public class Json {
private static final char COLON = ':'; // 0
private static final char O_BRACE = '{'; // 1
private static final char C_BRACE = '}'; // 2
private static final char COMMA = ','; // 3
// Others is 4
private static final int COLON_REP = 0;
private static final int O_BRACE_REP = 1;
private static final int C_BRACE_REP = 2;
private static final int COMMA_REP = 3;
private static final int OTHERS_REP = 4;
private static final int STATE_KEY = 0;
private static final int STATE_COLON = 1;
private static final int STATE_VALUE = 2;
private static final int STATE_COMMA = 3;
private static final int STATE_O_BRACE = 4;
private static final int STATE_C_BRACE = 5;
private static int getRepresentaion(char ch) {
switch(ch) {
case COLON:
return COLON_REP;
case O_BRACE:
return O_BRACE_REP;
case C_BRACE:
return C_BRACE_REP;
case COMMA:
return COMMA_REP;
default:
return OTHERS_REP;
}
}
private static int[][] buildDfa() {
int[][] dfa = new int[6][5];
for (int i = 0; i < dfa.length; i++) {
for (int j = 0; j < dfa[0].length; j++) {
dfa[i][j] = -1;
}
}
dfa[STATE_KEY][COLON_REP] = STATE_COLON;
dfa[STATE_COLON][OTHERS_REP] = STATE_VALUE;
dfa[STATE_COLON][O_BRACE_REP] = STATE_O_BRACE;
dfa[STATE_VALUE][COMMA_REP] = STATE_COMMA;
dfa[STATE_VALUE][C_BRACE_REP] = STATE_C_BRACE;
dfa[STATE_COMMA][OTHERS_REP] = STATE_KEY;
dfa[STATE_C_BRACE][COMMA_REP] = STATE_COMMA;
dfa[STATE_C_BRACE][C_BRACE_REP] = STATE_C_BRACE;
dfa[STATE_O_BRACE][OTHERS_REP] = STATE_KEY;
dfa[STATE_O_BRACE][C_BRACE_REP] = STATE_C_BRACE;
return dfa;
}
private static int getNextState(int[][] dfa, int curState, char ch) {
int rep = getRepresentaion(ch);
return dfa[curState][rep];
}
private static boolean countOAndCBrace(String text) {
int ocount = 0;
int ccount = 0;
for (Character c: text.toCharArray()) {
if (c == O_BRACE) {
ocount++;
}
else if (c == C_BRACE) {
ccount++;
}
}
return ocount == ccount;
}
private static boolean checkInput(String input) {
if (!countOAndCBrace(input)) {
System.out.println("Mismatching braces");
return false;
}
if (input.charAt(0) != O_BRACE) {
System.out.println("O_Brace");
return false;
}
int[][] dfa = buildDfa();
int state = STATE_O_BRACE;
for (int i = 1; i < input.length(); i++) {
state = getNextState(dfa, state, input.charAt(i));
if (state == -1) {
System.out.println("Wrong state");
return false;
}
}
if (state == STATE_C_BRACE) {
return true;
}
System.out.println("End");
return false;
}
public static void main(String[] args) {
if (args.length != 1) {
System.out.println("Please enter a correct input");
return;
}
String input = args[0];
if (checkInput(input)) {
System.out.println("Valid");
}
else {
System.out.println("Invalid");
}
}
}
public class ValidateJSONString {
public static void main(String[] args) {
System.out.println(isValidJSON("{a:b}"));
System.out.println(isValidJSON("{a:b, c:d}"));
System.out.println(isValidJSON("{a:b,c:{e:f}}"));
System.out.println(isValidJSON("{{a}}"));
System.out.println(isValidJSON("{{}}"));
System.out.println(isValidJSON("{}"));
System.out.println(isValidJSON("{a:b, c:dmomomo, f:efefefeokfoekfoekf, obj:{}}"));
System.out.println(isValidJSON("{a:b, , c:dm}"));
System.out.println(isValidJSON("{a:b, c:d:m}"));
}
public static boolean isValidJSON(String s) {
if (s == null || s.equals("") || s.length() <= 1) {
return false;
}
Stack<Character> stCBStart = new Stack<>();
StringBuilder temp = new StringBuilder();
char[] c = s.toCharArray();
int j = 0;
char cj;
for (int i = 0; i < c.length; i++) {
if (c[i] == '{') {
if (!stCBStart.isEmpty()) {
if (temp.length() != 0) {
j = temp.length()-1;
if (temp.charAt(j) != ':') {
return false;
}
cj = temp.charAt(j);
j--;
while(j >= 0 && cj != ',') {
cj = temp.charAt(j);
j--;
}
if (j == 0) {
temp = new StringBuilder();
} else if (j > 0 && cj == ',' && (j + 1) < temp.length()) {
temp.delete(j + 1, temp.length());
}
if (temp.length() > 0) {
if (!validateJSONStr(temp)) {
return false;
}
temp = new StringBuilder();
}
}
}
stCBStart.push('{');
} else if (c[i] == '}') {
if (stCBStart.isEmpty()) {
return false;
}
if (temp.length() > 0) {
if (!validateJSONStr(temp)) {
return false;
}
temp = new StringBuilder();
}
stCBStart.pop();
} else {
temp.append(c[i]);
}
}
if (stCBStart.size() > 0 || temp.length() > 0) {
return false;
}
return true;
}
private static boolean validateJSONStr(StringBuilder temp) {
String[] commas = temp.toString().split(",");
if (commas.length > 0) {
for (int i = 0; i < commas.length; i++) {
if (!isValidJSONExp(commas[i])) {
return false;
}
}
} else {
if (!isValidJSONExp(temp.toString())) {
return false;
}
}
return true;
}
private static boolean isValidJSONExp(String string) {
String[] groups = string.split(":");
return groups != null && groups.length == 2;
}
}
// output:
/*
true
true
true
false
true
true
true
false
false
*/
- Tarun December 02, 2015public static void main(String[] args) { // TODO Auto-generated method stub System.err.println(isValidJson("{a:b}")); System.err.println(isValidJson("{a:b, c:d}")); System.err.println(isValidJson("{a:b,c:{e:f}}")); System.err.println(isValidJson("{{a}}")); } private static boolean isValidJson(String string) { //Split by ',' first. Then go through each //Use Stack . If a } is encountered , pop each element from stack Stack<String> stack = new Stack<String>(); int ilen = string.length(); for(int i = 0 ; i < ilen; ++i) { char c = string.charAt(i); if ( c=='{') { stack.push(String.valueOf(c)); } else if (c==',') { if(!validateComma(stack)) return false; }else if ( c== '}'){ if(!validateBraces(stack)) return false; } else { stack.push(String.valueOf(c)); } } return true; } private static boolean validateBraces(Stack<String> stack) { String jsonTemp = new String(); boolean flag = true; while(flag) { String temp = stack.pop(); if(temp.equals("{")) { //Validate temp as valid String[] tempA = jsonTemp.split(":"); if (tempA.length != 2) return false; else return true; } jsonTemp = jsonTemp + temp; } return false; } private static boolean validateComma(Stack<String> stack) { //Means a new json string found. So extract each value till { is encontered String jsonTemp = new String(); boolean flag = true; while(flag) { String temp = stack.pop(); if(temp.equals("{")) { flag = false; stack.push("{"); //Validate temp as valid String[] tempA = jsonTemp.split(":"); if (tempA.length != 2) { return false; } else { return true; } } jsonTemp = jsonTemp + temp; } return false; }