堆栈未正确推送元素

Question

我正试图将字符串的部分推入两个不同的堆栈并弹出它们，以便我可以看到字符串是否平衡。例如，我们有((()))的样本输入，它会将(压入一个堆栈，并将)压入另一个堆栈。然后它将进入一个循环，弹出所有角色，如果两个堆栈都是空的，那么它将是平衡的。但是当我运行它的时候，我得到了这个。

Trying to pop when stack is empty
Trying to pop when stack is empty
Trying to pop when stack is empty
Trying to pop when stack is empty
Trying to pop when stack is empty
Trying to pop when stack is empty
true

我假设它没有正确地推送字符，我不知道为什么。这里有一个方法

static boolean isBalanced(String expr){
// base case: length of the expression must be even
if (expr == null || expr.length() % 2 == 1) {
return false;
}

Stack stack1 = new Stack();
Stack stack2 = new Stack();

// traverse the input expression
for (int i = 0; i< expr.length(); i++){ 
// if the current character in the expression is an opening brace,
// push it into the stack
if (expr.charAt(i) == '(') {
stack1.push(expr.charAt(i));
} 

// if the current character is closing brace
if (expr.charAt(i) == ')') {
stack2.push(expr.charAt(i));
}
}
for(int i = 0; i< expr.length(); i++) {
stack1.pop();
stack2.pop();
}
return (stack1.isEmpty() && stack2.isEmpty()) ; 
}

这是堆栈类

public class Stack{
private Node top;
public Stack() {
top = null;
}
public boolean isEmpty(){
return (top ==null);
}
public void push(Object newItem){
top = new Node(newItem,  top);
}
public Object pop(){
if (isEmpty()){
System.out.println(
"Trying to pop when stack is empty");
return null;
}else{
Node temp = top;
top = top.next;
return temp.info;
}
}

void popAll(){
top = null;
}
public Object peek(){
if (isEmpty()){
System.out.println(
"Trying to peek when stack is empty");
return null;
}else{  
return top.info;
}
}
}// End of Stack using a linked list

这里是节点类

public class Node {
Object info;
Node next;

Node(Object info, Node next){
this.info=info;
this.next=next;
}    
}

我不允许导入任何东西，我只允许改变方法，谢谢你

Answer 1

如果我对问题的理解是正确的，那么你的错误就在第二个for循环中。

for(int i = 0; i< expr.length(); i++) {
stack1.pop();
stack2.pop();
}

你将从每个堆栈中弹出exp .length()元素，因此两个堆栈在某一点上都将为空。

一个可能的解决方案是使用while循环，其循环条件是两个堆栈都不是空的。

当一个堆栈为空时，您停止循环，然后您的返回语句将正常工作，因为在一个堆栈为空的时刻，如果另一个堆栈也不为空，则表达式不平衡，如果它们都为空，则它们是平衡的(根据我从您对问题的定义中理解)

Answer 2

第二个for-loop:

...
for(int i = 0; i< expr.length(); i++) {
stack1.pop();
stack2.pop();
}
...

运行"太频繁"。在平衡的情况下，两个堆栈都持有expr.length() / 2- 5个元素，即它们在expr.length() / 2-pop()s之后是empty()，但我们pop()-expr.length()次。

这个问题可以很容易地通过用while环替换第二个for环来修复。我把确切的条件留给读者作为练习来弄清楚。