Pila de Paréntesis de Coincidencia [duplicar]

Question

Esta pregunta ya tiene las respuestas aquí:

Manejo paréntesis mientras que la conversión de expresiones infix a postfix expresiones (2 respuestas)

Cerrado Hace 2 años.

Así que estoy trabajando en algunas tareas con PostFix y Expresiones Infix.Estoy corriendo en un poco de un problema y parece que no puede encontrar donde tengo el problema.Puedo conseguir el Infijo a Postfijo de trabajo...para la mayor parte.Algunas de las ecuaciones que estoy recibiendo ( o ) impreso cuando yo no quiero ser impreso.También cuando tengo ninguna coincidencia entre paréntesis no me da un error como que yo quiero.

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;
}

Este es mi Infijo a Postfijo método

(((A + B) - (C - D)) / (E - F)) Esta es una de las expresiones que necesito resolver, y AB+CD--(EF-/ es lo que me sale cuando imprime en la pantalla. ((A es otro, este debería darme un error, pero A(( se imprime en la pantalla.

He estado corriendo la depuración por bastante tiempo y parece que no puede conseguir en cualquier lugar.

Cualquier ayuda sería muy útil.Sé que tiene algo que ver con el código publicado, pero no puedo encontrar el error de lógica.Gracias de antemano!

Así que he añadido una nueva función para ayudar con la coincidencia de paréntesis que creo que va a ser útil.Se toma la ecuación y sólo cuenta para ver si coinciden o no.

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

Para validar si el paréntesis está todo igualado, se puede ejecutar a través de su Cadena de entrada de la expresión matemática con un contador de valor inicial de 0, y si usted encuentra un (, incrementar el contador a 1, y en caso de encontrar un ), decrementamos el contador en 1.Si el contador llega a -1, romper, ya que no es válido el paréntesis partido.Al final, usted debe tener el valor del contador a 0.Si no, usted tiene un mal paréntesis.

Para el infijo a postfijo caso, he aquí un algoritmo estándar:

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

Bueno, me gustaría darle un poco de "ingeniería de software" de la punta, que al final puede resolver su problema y usted puede aprender mucho de hacer las cosas "bien".

Expresión matemática, no importa si escribes en el pre, en el post de la orden, se ve siempre la misma, si los guarda en alguna estructura de árbol.

Entonces, si usted quiere imprimir la estructura de árbol en la Cadena, usted sólo tiene que ir a través de todo el árbol, y varía sólo en el momento (y apoyos adicionales para algunos de los casos), cuando se escribe para esa cadena.

Preorder hacerlo cuando usted se vaya en ese nodo, a Finde cuando haya terminado la izquierda niño y Postorder, si lo haces al salir de ese nodo.

Mi consejo :

Clase : Expression, UnaryExpression extends Expression, BinaryExpression extedns Expression y entonces usted puede hacer números y operadores : Add extends BinaryExpression etc.

Entonces usted debe tener conocimiento de la clase Tree, que almacena el Expression root y tiene métodos printPreOrder(), printInOrder(), printPostOrder()

Para crear el árbol, sería realmente agradable de usar un Builder pattern que puede ser utilizado como esta :

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();
                    }
                    ...
                }
    }  

Y, a continuación, crear concreto el Generador de clases, que se parecen a este :

public class InOrderBuilder implements IExpressionBuilder {

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