Stack，圆括号匹配

Question

所以我正在用PostFix和Infix表达式做一些作业。我遇到了一些问题，似乎无法找到我遇到问题的位置。大部分我都可以通过Postfix工作。当我不希望它被打印时，我得到一些（或）打印的等式。另外，当我没有匹配的括号时，我不会收到像我想要的那样的错误。

public String Infix(String equation) throws Exception{ 
    Stack stack=new Stack(); 
    boolean parensMatch=false; 
    int priority=0; 
    String temp=""; 
    for(int i=0; i<equation.length(); i++){ 
     char c=equation.charAt(i); 
     //if the character is equal to left paren, push 
     if(c=='('){ 
      stack.push(c); 
     } 
     //if the character is equal to right paren, we start popping until we find a match 
     else if(c==')'){ 
      try{ 
       while(stack.peek()!='('){ 
        temp+=stack.pop(); 
       } 

       if(stack.peek()=='('){ 
        char ch=stack.pop(); 
        parensMatch=true; 
       } 

       if(parensMatch==false){ 
        throw new Exception("Parens Not Match Error"); 
       } 
      }catch(Exception e){ 
       System.out.println(e); 
      } 
      parensMatch=false; 
     } 
     //if the character is equal to an operator, we do some extra work 
     //to figure out what is going to happen 
     else if(c=='+' || c=='-' || c=='*' || c=='/' || c=='^'){ 
      char top=stack.peek(); 
      if(top=='^') 
       priority=2; 
      else if(top=='*' || top=='/') 
       priority=1; 
      else 
       priority=0; 
      if(priority==2){ 
       if(c=='*' || c=='/'){ 
        temp+=stack.pop(); 
       } 
       else if(c=='+' || c=='-'){ 
        temp+=stack.pop(); 
       } 
       else{ 
        temp+=stack.pop(); 
       } 
      } 
      else{ 
       if(c=='*' || c=='/'){ 
        temp+=stack.pop(); 
        stack.push(c); 
       } 
       else if(c=='+' || c=='-'){ 
        stack.push(c); 
       } 
       else{ 
        stack.push(c); 
       } 
      } 
     } 
     //if the character is a space, we ignore it and move on 
     else if(c==' '){ 
      ; 
     } 
     //if the character is a letter, we add it to the string 
     else{ 
      temp+=c; 
     } 
    } 
    int len = stack.size(); 
    for (int j = 0; j < len; j++) 
     temp+=stack.pop(); 
    return temp; 
} 

这是我对缀后缀方法

(((A + B) - (C - D))/(E - F))这是我需要解决的表情之一，AB+CD--(EF-/是我所得到的，当它打印到屏幕上。 ((A是另一个，这个应该给我一个错误，但A((被打印到屏幕上。

我一直在运行调试很长一段时间，似乎无法获得任何地方。

任何帮助将是非常有帮助的。我知道它与发布的代码有关，但我无法找到逻辑错误。提前致谢！

所以我添加了一个新的功能来帮助匹配parens，我认为它会很有用。它采用方程式并只计算它们是否匹配。

public static int matchingParens(String equation){ 
    int match=0; 

    for(int i=0; i<equation.length(); i++){ 
     char c=equation.charAt(i); 
     if(c=='(') 
      match++; 
     else if(c==')') 
      match--; 
     else 
      ; 
    } 

    return match; 
} 

Answer 1

为了验证是否括号都匹配了，你可以通过与0初始值的计数器的数学表达式你的字符串输入运行，如果你找到一个(，加1的计数器，如果你发现)，则将你的计数器减1。如果计数器达到-1，则发生，因为它不是有效的括号匹配。最后，您应该将计数器的值设为0.如果不是，则会有不匹配的括号。

对于缀以后缀的情况下，这里有一个标准的算法：

Define a stack 
Go through each character in the string 
If it is between 0 to 9, append it to output string. 
If it is left brace push to stack 
If it is operator *,+,- or/then 
      If the stack is empty push it to the stack 
      If the stack is not empty then start a loop: 
          If the top of the stack has higher precedence 
          Then pop and append to output string 
          Else break 
        Push to the stack 

If it is right brace then 
      While stack not empty and top not equal to left brace 
      Pop from stack and append to output string 
      Finally pop out the left brace. 

Answer 2

嗯，我想给你一些“软件工程”提示，这到底能解决你的问题，你可以学到很多东西通过做“很好”。

数学表达式，无论你是按照pre，in，post的顺序编写它们，看起来总是一样的，如果你将它们存储在某个树结构中的话。然后，如果要将该树结构打印到字符串中，则只需遍历整个树，并且只在当前时刻（以及某些情况下的其他大括号）变化时才会写入该字符串。

预订当您第一次进入该节点时执行此操作，当您完成左侧子节点和Postorder时，请执行此操作，如果您在离开节点时执行此操作。

我的建议是：

类：Expression，UnaryExpression extends Expression，BinaryExpression extedns Expression然后你就可以让数字和运算符：Add extends BinaryExpression等。

那么你应该有一流的Tree，它存储了Expression root，它有方法printPreOrder()，printInOrder()，printPostOrder()

要创建树，这将是非常不错的使用可以这样使用的Builder pattern：

public class Director { 
    private IExpressionBuilder builder; 

    public ArithmeticExpression construct(String text){ 
       for (int i=0;i<text.length();i++){ 
        if (text.charAt(i) == '+'){ 
         builder.buildAddOperator(); 
        } 
        ... 
       } 
    } 

，然后创建具体的生成器类，如下所示：

public class InOrderBuilder implements IExpressionBuilder { 

    public void buildAddOperator() { 
     ... 
    } 
    .... 
}