LeetCode 385. 迷你语法分析器

本文主要是介绍LeetCode 385. 迷你语法分析器，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：

力扣https://leetcode-cn.com/problems/mini-parser/

【分析】可以以 [ ] 为分界进行dfs分析

class Solution {public NestedInteger dfs(String s){NestedInteger ans = new NestedInteger();int n = s.length() - 1, i, j;String str = "";int t = 0;char c;for(i = 1; i < n; i++){c = s.charAt(i);if((c >= '0' && c <= '9') || c == '-'){str += c;}else if(c == '['){t++;str += c;}else if(c == ']'){t--;str += c;if(t == 0){ans.add(dfs(str));str = "";}}else if(c == ','){if(t == 0){if(str != ""){ans.add(new NestedInteger(Integer.parseInt(str)));}str = "";}else{str += c;}}}if(str != "" && t == 0) ans.add(new NestedInteger(Integer.parseInt(str)));return ans;}public NestedInteger deserialize(String s) {if(s.charAt(0) != '['){return new NestedInteger(Integer.parseInt(s));}return dfs(s);}
}

【方法二 栈】 用栈来模拟这个过程的话，有种情况

1.首先遇到 ' [ ' 就往栈里添加一个新的NestedIntger对象

2.遇到 ' - ' 记录数字的正负

3.遇到 ‘0’ - ‘9’ 生成数字，并用标记记录此时有数字生成

4.遇到 ' , ' 把数字封装成NestedIntger对象并添加到栈顶的对象中

5.遇到 ' ] ' 把栈顶对象合并到他左边的对象中去

  

/*** // This is the interface that allows for creating nested lists.* // You should not implement it, or speculate about its implementation* public interface NestedInteger {*     // Constructor initializes an empty nested list.*     public NestedInteger();**     // Constructor initializes a single integer.*     public NestedInteger(int value);**     // @return true if this NestedInteger holds a single integer, rather than a nested list.*     public boolean isInteger();**     // @return the single integer that this NestedInteger holds, if it holds a single integer*     // Return null if this NestedInteger holds a nested list*     public Integer getInteger();**     // Set this NestedInteger to hold a single integer.*     public void setInteger(int value);**     // Set this NestedInteger to hold a nested list and adds a nested integer to it.*     public void add(NestedInteger ni);**     // @return the nested list that this NestedInteger holds, if it holds a nested list*     // Return empty list if this NestedInteger holds a single integer*     public List<NestedInteger> getList();* }*/
class Solution {public NestedInteger deserialize(String s) {if(s.charAt(0) != '[') return new NestedInteger(Integer.parseInt(s));Stack<NestedInteger> stack = new Stack();int n = s.length(), i, num = 0, flag = 1, has_num = 0;char c;for(i = 0; i < n; i++){c = s.charAt(i);if(c == '['){stack.push(new NestedInteger());}else if(c == '-'){flag = -1;}else if(c >= '0' && c <= '9'){num = num * 10 + c - '0'; has_num = 1;}else if(c == ']' || c == ','){if(has_num == 1){stack.peek().add(new NestedInteger(flag * num));num = 0; flag = 1; has_num = 0;}if(c == ']'){if(stack.size() > 1){NestedInteger ni = stack.pop();stack.peek().add(ni);}}}}return stack.peek();}
}

 

 

这篇关于LeetCode 385. 迷你语法分析器的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---