使用堆栈检查在java中匹配的括号

Question

嗨，大家伙我想创建一个程序，以允许用户输入一个括号序列（一次一个），并检查是否有一个相应的结束括号。括号每次输入一个新行以帮助阅读。我已经为它设置了ADT，但只是不能想到如何获得while循环和检查......我知道如果（括号被输入，我应该将它推入堆栈，并且当（是进入我应该弹出堆栈之一，但我只是不能工作了位在中间的任何帮助，将喜爱:)

//main code 
import java.util.*; 

public class SameBrackets 
{ 
    public static void main(String[] args) 
    { 
     Stack bracket = new Stack(); 
     Scanner kybd = new Scanner(System.in); 

     System.out.print("Enter bracket > "); 
     String bracketentered = kybd.next(); 


      if ("(".equals(bracketentered)) 
      { 
       bracket.push(bracketentered); 
       System.out.println(") needed"); 
      } 
      else if (")".equals(bracketentered)) 
      { 
       bracket.pop(); 
       System.out.println("(needed"); 
      } 


     } 
    } 

// ADT代码

public class Stack 
{ 
    private String[] a;   //String array 
    private int top; 

    public Stack() 
    { 
     a = new String[1];   //create String array 
     top = 0;      
    } 

    public boolean isEmpty() 
    { 
     return top == 0; 
    } 

    public String pop()   //pop String element 
    { 
     top--; 
     return(a[top]);   //underflow not protected 
    } 

    public void push(String x)  //push String element 
    { 
     if (top == a.length) 
     { 
      resize(); 
     } 
     a[top] = x; 
     top++; 
    } 

    private void resize() 
    { 
     String[] temp = new String[a.length * 2]; //resize String array 
     for (int i = 0; i < a.length; i++) 
     { 
      temp[i] = a[i]; 
     } 
     a = temp; 
    } 
} 

Answer 1

• 你为什么需要一个堆栈？你可以只有一个计数器，在''上递增'''' - 每次递减时确保它的值仍然是非负数。
• 不知道你对循环的问题是什么。你可以有一个由特定输入终止的while循环（例如 - 'q'）。

---

至于你的循环问题：

input = getInput(scanner); 
while(input != null) { 
    // do what you want with the input 

    input = getInput(scanner); 
} 

private static String getInput(Scanner scanner) { 
    get the input from the scanner here - return null if no more input. 
} 

Answer 2

你是否在寻找类似：

if ("(".equals(bracketentered)) { 
    bracket.push(bracketentered); 
} else if (")".equals(bracketentered)) { 
    bracket.pop(); 
} 
if (bracket.isEmpty()) { 
    System.out.println("(needed"); 
} else { 
    System.out.println(") needed"); 
} 

Answer 3

你不需要实现自己的堆栈，一个LinkedList（特别是它实现的接口Deque）可以做到这一点。但这是一个很好的练习。

您的代码缺少两件事。

• 一个循环，直到达到某个终点。不幸的是，当您从控制台输入文本时，不容易达到System.in的末尾。它通常是可以结束的Ctrl-D。添加自己的停止机制是一个好主意，大多数人不知道如何结束程序。
• 您需要检查弹出堆栈的支架是否与刚输入的支架相匹配。
• 您应该检查堆栈实际上是否为空。

如果你这样做，你最终像

// a stack. You can use your own instead. 
Deque<String> stack = new LinkedList<String>(); 
Scanner kybd = new Scanner(System.in); 

String bracketentered; 

// 1) repeat while there is more, CTRL-D should end here. 
while (kybd.hasNext()) { 
    System.out.print("Enter bracket or 'q' to quit:"); 
    bracketentered = kybd.next(); 

    if (bracketentered.equals("q")) { 
     break; // end this loop 
    } 

    if ("(".equals(bracketentered)) { 
     // just push to stack 
     stack.push(bracketentered); 
    } 
    else if (")".equals(bracketentered)) { 
     // in case the stack is empty: 
     // stack.pop() throws an exception 
     // stack.poll() returns null 
     String opposingBracket = stack.poll(); 

     // there must be a "(" on the stack(
     if (!"(".equals(opposingBracket)) { 
      System.out.println("Wrong bracket"); 
     } 
    } 
    else { 
     // in case it's not (or) 
     System.out.println("Illegal input:" + bracketentered); 
    } 
} 
// 3) loop finished via "q" or end of input - check that stack is empty 
if (!stack.isEmpty()) { 
    System.out.println("You forgot to close the following brackets:"); 
    while (!stack.isEmpty()) { 
     System.out.print(stack.poll() + " "); 
    } 
    System.out.println(); 
} 

---

关于循环叠VS计数括号：只有在最后检查一个非常简单的支架计数算法将允许) ( ，在每个步骤中检查的更聪明的人可能会失败，如[ (])多支架组合。堆栈确保它们是正确分层的，例如， [() ]。