如何评价使用堆栈只是一个扫描中缀表达式？(How to evaluate an infix expr

我想知道是否有解决使用2个堆栈单程缀表达式的方法吗？ 该堆栈可以是一个为运营商和其他操作数...

由分路码算法来解决的标准方法是，将缀表达式转换为后缀（逆波兰），然后解决。 我不想表达先转换为后缀。

如果表达式等2*3-(6+5)+8 ，如何解决？

Answer 1:

已经很晚了，但在这里就是答案。

就拿两个栈：

1. operator stack {为运营商和括号}。
2. operand stack 。

算法

如果字符存在要读：

1. 如果字符是operand的上推operand stack ，如果字符是( ，推动对operator stack 。
2. 否则，如果字符是operator
   1. 虽然顶部operator stack比这个人物更小的优先级没有。
   2. 流行operator从operator stack 。
   3. 弹出两个operands （ op1和op2从） operand stack 。
   4. 商店op1 op op2的operand stack回2.1。
3. 否则，如果字符) ，做一样的2.2 - 2.4直到你遇到( 。

其他（没有更多的文字留下来读）：

• 流行音乐运营商，直到operator stack不为空。
• 弹出顶部2 operands和push op1 op op2的上operand stack 。

返回从顶部值operand stack 。

Answer 2:

在给出的方法链接是非常好的。

让我引用来源：

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.

我希望这有帮助！

Answer 3:

1. 创建一个空的运营商栈。
2. 创建一个空操作数堆栈。
3. 在输入字符串中的每个令牌
   一个。 得到的缀串的下一个标记。
   湾 如果下一个是一个操作数，将其放置在操作数栈上。
   C。 如果下一个标记是一个操作符
   • 评估操作。
4. 而运营商堆栈不为空，（左，右）弹出操作和操作数，评估左右运营商推到导致操作数栈。
5. 从运营商栈弹出的结果。

Answer 4:

下面是我在Java中缀表达式求值的尝试。 请让我知道如果你发现任何错误:)

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

文章来源: How to evaluate an infix expression in just one scan using stacks?