括号Java组输入的有效括号匹配方法
编辑:我应该提到程序必须是严格非递归的
我正在尝试创建一个方法,将组分配给匹配的括号。例如,输入:m (a (b c) (d (e (f g h) i) j) k) n
输出为:
Inputted text: m (a (b c) (d (e (f g h) i) j) k) n
group 0 = m (a (b c) (d (e (f g h) i) j) k) n
group 1 = (a (b c) (d (e (f g h) i) j) k)
group 2 = (b c)
group 3 = (d (e (f g h) i) j)
group 4 = (e (f g h) i)
group 5 = (f g h)
我创建了以下方法,但正如您所看到的,它将第一个遇到的左括号与第一个遇到的右括号相匹配,而不是每个左括号表示新组的开始。我无法找到一种简单的方法来复制上述输出而不重新开始。有什么想法吗
public class Matching {
public static String[] group(String s){
Stack<Integer> indexStack = new Stack<Integer>();
String[] groupArray = new String[15];
int count = 0;
for(int i = 0; i != s.length(); i++){
/*
* If character in index position is a left parenthesis, push the current
* index onto stack. If a right parenthesis is encountered, pop the stack and
* store its index temporarily. Use index and current position at right
* parenthesis to create a substring.
*/
if(s.charAt(i) == '(')
indexStack.push(i);
else if( s.charAt(i) == ')' ){
try{
int index = indexStack.pop();
groupArray[count++] = s.substring(index, i + 1);
}
catch(Exception e){ //An exception results from popping empty stack
System.out.println("Unbalanced in input " + s +
" at index " + i + "\n");
return null; //return null to caller
}
}
}
//If stack not empty at the end of loop, return null to caller
if(!indexStack.isEmpty()){
System.out.println("Unbalanced in input " + s +
" at index " + indexStack.pop() + "\n");
return null;
}
//initial input that starts with a character other than ( needed to be added.
if (s.charAt(0) != '(')
groupArray[count++] = s;
return groupArray;
}
}
# 1 楼答案
我使用另一个数组来跟踪左括号中出现的情况,为这个问题添加了一个非常糟糕的修复方法。如果我的教授看到了我没有作弊
# 2 楼答案
不需要使用递归。 如果输出元素的顺序不受限制,则尝试使用此选项(请注意,输入中的所有字符都有一次迭代):
输出
p.S. 算法假设输入格式正确——不均匀的
(
和)
计数可能会导致EmptyStackException
# 3 楼答案
更好的方法是使用正则表达式和递归。这减少了代码长度,并利用了java提供的实用程序
# 4 楼答案
当我更改代码的输入时,我遇到了一个错误。此外,在
sys.out
上还有多余的空值我没有试图修复您的代码,但以下是一种分组方法:
你会得到开始&;组的结束点,然后您可以根据需要
sys.out