Conversion from Infix to Fixed Value

Question

I have to convert an Infix value to Posfixo

Examples:

The problem with my algorithm is that last line.... I believe the problem is in expressions with + 2 terms within parentheses, like: (X * Y + Z)

Honestly, I’ve debugged the code several times, I’ve changed to several versions and still can’t fix..... any suggestion?

FOLLOWS BELOW THE COMPLETE CODE:

function operando(caracter){
    var regex = /^[a-zA-Z]+$/;
    if(regex.test(caracter)){
        return true;
    }else{
        return false;
    }
}

function operador(caracter){
    var regex = /^[*+-–/^]+$/gi;
    if(regex.test(caracter)){
        return true;
    }else{
        return false;
    }
}

function obterPrioridade(caracter){
    var retorno= 0;
    var regex1 = /^[+-–]+$/gi;
    var regex2 = /^[*/]+$/gi;

    if('(' == caracter){
        retorno = 1;
    }else if(regex1.test(caracter)){
        retorno = 2;
    }else if(regex2.test(caracter)){
        retorno = 3;
    }else if ('^' == caracter){
        retorno = 4;
    }
    return retorno;
}

function transformar(){
    //Converte uma expressão da forma Infixa na forma Posfixa. Segue a lógica explica anteriormente na introdução sobre expressões
    var arrayDeCaracteres = document.getElementById("expressao").value;
    var pilha = [];
    var prioridade = 0;
    var caracter = ""; var resultado = "";

    //Varre todos os elementos da expressão de entrada e, para cada elemento, verifica se é operador ou operando. Se for operando, já adicona a saída
    for(i = 0; i < arrayDeCaracteres.length; i++){
        caracter = arrayDeCaracteres.charAt(i);

        if(operando(caracter)){
            resultado += caracter;
        }else if(operador(caracter)){
            prioridade = obterPrioridade(caracter);
            aux = pilha.pop();
            prioridade2 = obterPrioridade(aux);
            //alert('Caracter: '+caracter+'\n'+prioridade+'\nAux: '+aux+'\n'+prioridade2);
            pilha.push(aux);
            if(typeof aux === 'undefined'){
            }else{
                while((pilha.length > 1) && (prioridade2 >= prioridade)){
                    resultado += pilha.pop();
                }
            }
            pilha.push(caracter);
        }else if('(' === caracter){
            //Insere o objeto no topo da pilha
            pilha.push(caracter);
        }else if(')' === caracter){
            var item = pilha.pop();
            while ((item != '(') && (item != undefined)){
                resultado += item;
                //Recupera e remove o objeto do topo da pilha
                item = pilha.pop();
            }
        }
    }

    while(pilha.length > 1){
        resultado += pilha.pop();
    }

    console.log(resultado);
}

I believe the error of logic lies in this passage:

        }else if(')' === caracter){
            var item = pilha.pop();
            while ((item != '(') && (item != undefined)){
                resultado += item;
                //Recupera e remove o objeto do topo da pilha
                item = pilha.pop();
            }
        }

Answer 1

It’s a pretty simple mistake you missed. There’s nothing wrong with the code or the algorithm itself, it works. Error is in regular expressions.

As well used in function operando, it is possible to write [A-Z] to denote all characters between A and Z. The problem is when you write something like this: /^[*+-–/^]+$/.

Look over there: [+-–]. This is capturing a whole string between the + and the –. The solution, in this case, is to move the - (minus) to the end, or to the beginning.

Thus: /^[-*+–/^]+$/. The same happens in the function obterPrioridade.

I tested and with this simple change the code works.