Как оценить инфиксное выражение всего за один просмотр, используя стеки?

Я хочу знать, есть ли способ решить инфиксные выражения за один проход, используя 2 стека? Стеки могут быть один для оператора, а другой для операндов ...

Стандартный способ решения с помощью алгоритма шунтирующего двора - преобразовать выражение инфикса в постфикс (обратная полировка), а затем решить. Я неЯ не хочу сначала преобразовывать выражение в постфикс.

Если выражение похоже2*3-(6+5)+8, как решить?

Ответы на вопрос(4)

создать пустой стек операторов.создать пустой стек операндов.для каждого токена во входной строке

а. получить следующий токен в инфиксной строке.

б. если следующий операнд, поместите его в стек операндов.

с. если следующий токен является операторомОцените оператора.в то время как стек операторов не пустой, оператор pop и операнды (левый и правый) оценивают левый оператор right и помещают результат в стек операндов.поп результат из стека операторов.
 user20742129 окт. 2015 г., 11:09
Здесь нет упоминания о приоритетах операторов.

ссылка это действительно хорошо.

Позвольте мне процитировать источник:

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.

Надеюсь, это поможет!

Решение Вопроса

Возьмите два стека:

operator stack {для операторов и скобок} ..operand stackАлгоритм

Если символ существует для чтения:

Если персонажoperand нажать наoperand stackесли персонаж(Нажимай на.operator stackИначе, если персонажoperatorХотя вершинаoperator stack имеет не меньший приоритет, чем этот символ.попoperator от .operator stackПоп два (operandsop1 а такжеop2) от .operand stackхранитьop1 op op2 наoperand stack вернуться к 2.1.Иначе, если персонаж)делайте то же самое, что и 2.2 - 2.4, пока не встретите.(

Остальное (больше не осталось символов для чтения):

Поп операторы доoperator stack не пустоPop top 2operands а такжеpush op1 op op2 на .operand stack

вернуть верхнее значение из. "operand stack

 user20742111 окт. 2014 г., 01:56
Это безымянное изложение алгоритма Dijkstra Shunting-ярд, Edsger Dijkstra, 1960. -1 для исключения атрибуции.
 Rohit21 янв. 2014 г., 13:03
спасибо, позвольте мне проверить. В офисе прямо сейчас ..
 David Nogueira19 авг. 2016 г., 20:40
для любого заинтересованного народа шаг 1 должен быть1. если символ является операндом или (. Нажмите в стеке: если операндом нажмите операндStack и если (в operatorStack. "
 KurinchiMalar08 февр. 2016 г., 18:24
Очень важная часть алгоритма для работы, как сказал @Gyfis " если input является a): 1 В то время как верхняя часть стека операторов не является (: "
 damianesteban12 июн. 2015 г., 05:32
Ничего себе, давая -1 для этого за пределами неприятного.
 Neo M Hacker11 февр. 2016 г., 00:46
@ Rohit: похоже, у вас есть ошибка (опечатка)если символ является операндом или (. нажмите на operandStack ". '(' должен быть помещен в стек оператора, а не в operandStack.
 user20742129 окт. 2015 г., 11:09
@Rohit Презумпция подавляющая.
 Neo M Hacker11 февр. 2016 г., 00:44
@EJP Джикстра - великий ученый, но я думаю, что студенты могут придумать этот алгоритм, особенно учитывая подсказку использовать два стека.
 Rohit15 окт. 2014 г., 00:44
@EJP никогда не слышал ни о каком алгоритме маневрового двора. Я сам придумал этот алгоритм, и может быть, Дейкстра придумал это еще до меня. Я бы сделал это иначе ... Вместо того, чтобы спрашивать меня первым и давать ему -1 только после подтверждения со мной, я призываю вас доказать, что я не мог придумать этот алгоритм сам, и этот текст адаптирован или скопирован откуда-то Я был бы рад внести необходимые изменения в этом случае. Спасибо
 Vipin15 мая 2016 г., 13:31
После двух стековых подсказок студенты могут написать это сегодня (время - важная часть)
 don bright07 мар. 2019 г., 05:45
я не -1, потому что это так же, как Djisktra, я -1, потому что это нет работа. В этом алгоритме нет нигде, где бы оператор помещался в стек операторов, что является основополагающим для его работы. Это не должно быть принятым ответом, и все эти отрицательные отзывы неверны.
 Rohitashwa Nigam02 апр. 2019 г., 20:00
Исправление: "сохранить / нажать op2 op op1 в стеке операндов » скорее, чем "сохранить / нажать op1 op op2 в стеке операндов ", Этот порядок будет иметь значение для операторов, таких как экспонента и т. Д.
 Gyfis20 янв. 2014 г., 18:03
[делай так же, как 2, пока не встретишь)   - там должен быть '(' вместо ')' Я верю! (эта опечатка в моем алгоритме вызвала некоторые головные боли !!)

дайте мне знать, если вы найдете какие-либо ошибки :)

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;
        }
    }
}
</character></character></character></character></long></character></long>

Ваш ответ на вопрос