java - 堆栈、括号匹配

Question

这个问题已经有答案了:

Handling parenthesis while converting infix expressions to postfix expressions (2 个回答)

已关闭 6 年前。

所以我正在做一些关于 PostFix 和 Infix 表达式的作业。我遇到了一些问题，似乎无法找到问题出在哪里。我可以让 Infix to 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;
}

这是我的 Infix 到 Postfix 方法

(((A + B) - (C - D)) / (E - F))这是我需要解决的表达式之一，并且 AB+CD--(EF-/这是我在打印到屏幕上时得到的。 ((A是另一个，这个应该给我一个错误，但是 A((打印到屏幕上。

我已经运行调试很长一段时间了，但似乎没有任何进展。

任何帮助都会非常有帮助。我知道它与发布的代码有关，但我找不到逻辑错误。提前致谢!

所以我添加了一个新函数来帮助匹配括号，我认为这会很有用。它采用等式并计算它们是否匹配。

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.