使用堆栈测试平衡分隔符

Question

我做了一个基于单个链表的通用堆栈类，并试图用它来检查用户输入的平衡分隔符。我只是检查这些分隔符：（）{} []

栈代码

public class SLStack<T> { 

//initializes the first node 
private SLStackNode<T> head; //initializes the first node 

//constructor initializes the first node as null to simulate an empty stack 
public SLStack(){ 
    head = null; 
} 

//inner node class 
public static class SLStackNode<T>{ 
    public T data; 
    public SLStackNode<T> next; 
} 

//adds an element to the top of the stack 
public void push(T value){ 
    SLStackNode<T> newNode = new SLStackNode<>(); 
    newNode.data = value; 
    newNode.next = head; 
    head = newNode; 
} 

//removes an element from the top of the stack 
public T pop(){ 
    if (head == null){ 
     throw new IllegalStateException("The list is empty."); 
    } 
    T value = head.data; 
    head = head.next; 
    return value; 
} 

//checks the element at the top of the stack 
public T top(){ 
    if (head == null){ 
     throw new IllegalStateException("The list is empty."); 
    } 
    T value = head.data; 
    return value; 
} 

public boolean isEmpty(){ 
    return head == null; 
} 


public void printStack(SLStackNode<T> node, int depth) { 
    if (node.next != null) { 
     System.out.println(depth + " : " + node.data); //recurses through the stack 
     //printStack(node.next); 
    } 
    System.out.println(depth + " : " + node.data); //recursive base case 
} 
} 

平衡测试仪典

public class Balanced { 
public static void main(String[] args) 
{ 
    SLStack<ExpressionScanner.Token> delimStack = new SLStack<>(); 
    System.out.println("Enter one expression per line."); 
    System.out.println("End the program with a period on a line by itself."); 
    ExpressionScanner escan = new ExpressionScanner(new Scanner(System.in)); 
    while (escan.hasNext()) { 
     ExpressionScanner.Token token = escan.next(); 

     if (token.getType() == ExpressionScanner.Token.Type.OP || token.getType() == ExpressionScanner.Token.Type.VAR){ 
      //ignore these tokens 
      continue; 
     } 

     if (token.getType() == ExpressionScanner.Token.Type.DELIM_OPEN){ 
      //push opening delimiter to the stack 
      delimStack.push(token); 
     } 

     if (token.getType() == ExpressionScanner.Token.Type.DELIM_CLOSE){ 
      //look for matching opening delimiter in the stack and pop it from the stack 
      if (token == delimStack.top()){ 
       delimStack.pop(); 
      }else{ 
       throw new IllegalStateException("Imbalanced delimiter detected."); 
      } 
     } 

     if (delimStack.isEmpty()){ 
      System.out.println("Delimiters are balanced."); 
     }else{ 
      System.out.println("Imbalanced delimiter detected."); 
     } 

     //System.out.println(token); 
    } 
} 
} 

当我运行它总是说，分隔符不均衡没有测试仪不管它是什么。即使做一个单独的分隔符也会导致它说不平衡，但它不会抛出异常。它会在单个结束分隔符处或者如果有多个结束分隔符时抛出异常。如果我有两个开始分隔符，它也不会终止。

如果有人需要它，我也可以发布ExpressionScanner的代码。

Answer 1

  if (token == delimStack.top()){ 
      delimStack.pop(); 
     }else{ 
      throw new IllegalStateException("Imbalanced delimiter detected."); 
     } 

如果我认为正确的代码抛出这里例外，因为它需要使用类型为DELIM_CLOSE的令牌，但接收DELIM_OPEN（前提是您的输入为“（）”）。

你应该检查什么是是否delimStack.pop（）= token.type.DELIM_OPEN。