infix-notation - postfija - notacion prefija arboles

¿Cómo evaluar una expresión de infijo en solo un escaneo usando stacks?

Question

Quiero saber si hay una forma de resolver expresiones infija en un solo pase usando 2 pilas. Las pilas pueden ser una para el operador y la otra para operandos ...

La forma estándar de resolver mediante algoritmo de yarda de derivación es convertir la expresión de infijo a postfijo (pulido inverso) y luego resolver. No quiero convertir la expresión primero a postfix.

Si la expresión es como 2*3-(6+5)+8 , ¿cómo resolverlo?

Answer 1

1. crea una pila de operador vacía.
2. crea una pila de operandos vacía.
3. para cada token en la cadena de entrada
   a. obtener el siguiente token en la cadena infija.
   segundo. si el siguiente es un operando, colóquelo en la pila de operandos.
   do. si el siguiente token es un operador
   • Evaluar al operador
4. mientras que la pila del operador no está vacía, opere pop y operandos (izquierda y derecha), evalúe el operador izquierdo a la derecha y coloque el resultado en la pila de operandos.
5. pop resultado de la pila del operador.

Answer 2

A continuación se muestra mi intento de evaluación de expresiones infija en java. Por favor, avíseme si encuentra algún error :)

import java.util.*;

public class ArithmeticExpressionEvaluation {

    public static void main(String[] args) {
        Scanner readExpression = new Scanner(System.in);
        System.out.print("Enter the expression: ");
        String expression = readExpression.nextLine();
        System.out.println(expression);
        System.out.println("Result: " + calculateExpression(expression));
    }

    public static long calculateExpression(String expression) {

        Stack<Long> operandStack = new Stack<>();
        Stack<Character> operatorStack = new Stack<>();

        if (!isValidExpression(expression)) {
            System.out.println("Not a valid expression to evaluate");
            return 0;
        }

        int i = 0;
        String currentInteger = null;
        while (i < expression.length()) {

            // System.out.println(expression.charAt(i));
            if (expression.charAt(i) >= ''0'' && expression.charAt(i) <= ''9'') {

                currentInteger = expression.charAt(i) + "";
                i++;
                while (i != expression.length() && (expression.charAt(i) >= ''0'' && expression.charAt(i) <= ''9'')) {
                    currentInteger = currentInteger + expression.charAt(i);
                    i++;
                }

                operandStack.push(Long.parseLong(currentInteger));
            } else {

                if (expression.charAt(i) == '')'') {

                    while (operatorStack.peek() != ''('') {
                        performArithmeticOperation(operandStack, operatorStack);
                    }
                    operatorStack.pop();
                } else {

                    Character currentOperator = expression.charAt(i);
                    Character lastOperator = (operatorStack.isEmpty() ? null : operatorStack.peek());


                    if (lastOperator != null && checkPrecedence(currentOperator, lastOperator)) {
                        performArithmeticOperation(operandStack, operatorStack);
                    }
                    operatorStack.push(expression.charAt(i));

                }
                i++;
            }

        }


        while (!operatorStack.isEmpty()) {
            performArithmeticOperation(operandStack, operatorStack);
        }

    //    System.out.println(Arrays.toString(operandStack.toArray()));
    //    System.out.println(Arrays.toString(operatorStack.toArray()));

        return operandStack.pop();

    }

    public static void performArithmeticOperation(Stack<Long> operandStack, Stack<Character> operatorStack) {
        try {
            long value1 = operandStack.pop();
            long value2 = operandStack.pop();
            char operator = operatorStack.pop();

            long intermediateResult = arithmeticOperation(value1, value2, operator);
            operandStack.push(intermediateResult);
        } catch (EmptyStackException e) {
            System.out.println("Not a valid expression to evaluate");
            throw e;
        }
    }


    public static boolean checkPrecedence(Character operator1, Character operator2) {

        List<Character> precedenceList = new ArrayList<>();
        precedenceList.add(''('');
        precedenceList.add('')'');
        precedenceList.add(''/'');
        precedenceList.add(''*'');
        precedenceList.add(''%'');
        precedenceList.add(''+'');
        precedenceList.add(''-'');


        if(operator2 == ''('' ){
            return false;
        }

        if (precedenceList.indexOf(operator1) > precedenceList.indexOf(operator2)) {
            return true;
        } else {
            return false;
        }

    }

    public static long arithmeticOperation(long value2, long value1, Character operator) {

        long result;

        switch (operator) {

            case ''+'':
                result = value1 + value2;
                break;

            case ''-'':
                result = value1 - value2;
                break;

            case ''*'':
                result = value1 * value2;
                break;

            case ''/'':
                result = value1 / value2;
                break;

            case ''%'':
                result = value1 % value2;
                break;

            default:
                result = value1 + value2;


        }
        return result;
    }


    public static boolean isValidExpression(String expression) {

        if ((!Character.isDigit(expression.charAt(0)) && !(expression.charAt(0) == ''(''))
                || (!Character.isDigit(expression.charAt(expression.length() - 1)) && !(expression.charAt(expression.length() - 1) == '')''))) {
            return false;
        }

        HashSet<Character> validCharactersSet = new HashSet<>();
        validCharactersSet.add(''*'');
        validCharactersSet.add(''+'');
        validCharactersSet.add(''-'');
        validCharactersSet.add(''/'');
        validCharactersSet.add(''%'');
        validCharactersSet.add(''('');
        validCharactersSet.add('')'');

        Stack<Character> validParenthesisCheck = new Stack<>();

        for (int i = 0; i < expression.length(); i++) {

            if (!Character.isDigit(expression.charAt(i)) && !validCharactersSet.contains(expression.charAt(i))) {
                return false;
            }

            if (expression.charAt(i) == ''('') {
                validParenthesisCheck.push(expression.charAt(i));
            }

            if (expression.charAt(i) == '')'') {

                if (validParenthesisCheck.isEmpty()) {
                    return false;
                }
                validParenthesisCheck.pop();
            }
        }

        if (validParenthesisCheck.isEmpty()) {
            return true;
        } else {
            return false;
        }
    }
}

Answer 3

El método dado en el enlace es realmente bueno.

Déjame citar la fuente:

We will use two stacks:

Operand stack: to keep values (numbers)  and

Operator stack: to keep operators (+, -, *, . and ^).  


In the following, “process” means, (i) pop operand stack once (value1) (ii) pop operator stack once (operator) (iii) pop operand stack again (value2) (iv) compute value1 operator  value2 (v) push the value obtained in operand stack.          


Algorithm:


Until the end of the expression is reached, get one character and perform only one of the steps (a) through (f):

(a) If the character is an operand, push it onto the operand stack.

(b) If the character is an operator, and the operator stack is empty then push it onto the operator stack.

(c) If the character is an operator and the operator stack is not empty, and the character''s precedence is greater than the precedence of the stack top of operator stack, then push the character onto the operator stack.

(d) If the character is "(", then push it onto operator stack.

(e) If the character is ")", then "process" as explained above until the corresponding "(" is encountered in operator stack.  At this stage POP the operator stack and ignore "(."

(f) If cases (a), (b), (c), (d) and (e) do not apply, then process as explained above.



 When there are no more input characters, keep processing until the operator stack becomes empty.  The values left in the operand stack is the final result of the expression.

¡Espero que esto ayude!

Answer 4

Muy tarde, pero aquí está la respuesta.

Toma dos pilas:

1. operator stack {para operadores y paréntesis}.
2. operand stack .

Algoritmo

Si el personaje existe para ser leído:

1. Si el carácter es operand presione en la operand stack del operand stack , si el carácter es ( , presione en la operator stack .
2. Si el personaje es el operator
   1. Mientras que la parte superior de la operator stack del operator stack no es de menor prioridad que este carácter.
   2. operator Pop de la operator stack del operator stack .
   3. Pop dos operands ( op1 y op2 ) de la operand stack .
   4. Almacene op1 op op2 en la operand stack nuevo a 2.1.
3. Si el personaje es ) , haga lo mismo que 2.2 - 2.4 hasta que encuentre ( .

De lo contrario (no queda más personaje para leer):

• Los operadores Pop hasta la operator stack no están vacíos.
• Pop top 2 operands y push op1 op op2 en la operand stack .

devuelve el valor superior de la operand stack .