Tính toán biểu thức trung tố

Chào mọi người cho em hỏi tí ạ.
Ví dụ em nhập vào chuỗi sau: 2*(5*10)+5-20/4
Thì muốn tính toán phép tính trên thì em phải xử lý như thế nào ạ?
Em cảm ơn!

Ngôn ngữ gì vậy bạn ?

1 Like

Chúng ta hãy xét biểu thức trong ví dụ trên

Q=“a*(b+c)-d^5”

Ký hiệu biểu thức ghi dưới dạng phép toán sau là P. Trong quá trình chuyển đổi ta dùng một stack S để lưu các phần tử trong P chưa sử dụng đến. Khi đọc từ trái sang phải biểu thức Q la lần lượt có:

Đọc và ghi nhận giá trị a, ghi giá trị a vào P. Vậy P = "a".
Đọc toán tử "*". Đưa toán tử này vào stack S: S = "*"
Đọc dấu ngoặc mở "(", đưa dấu ngoặc này vào stack: S = "* (".
Đọc hạng tử b, đưa b vào P: P = "a b"
Đọc toán tử "+", đặt "+" vào stack: S = "* ( +"
Đọc hạng tử "c", đưa c vào cuối P: P = "a b c"
Đọc dấu ngoặc đóng ")". Lần lượt lấy các toán tử ở cuối stack ra khỏi stack đặt vào cuối P cho đến khi gặp dấu ngoặc mở "(" trong stack thì giải phóng nó: S = "*"; P = "a b c +"
Đọc toán tử "-". Cuối stack S có toán tử "*" có mức ưu tiên lớn hơn toán tử "-", ta lấy toán tử "*" ra khỏi stack, đặt vào cuối P, đặt toán tử "-" vào stack: S = "-"; P = "a b c + *"
Đọc hạng tử "d", đưa d vào cuối P. P = "a b c + * d"
Đọc toán tử "^", đưa toán tử "^" vào cuối stack: S = "- ^"
Đọc hằng số "5", đưa 5 vào cuối P: P = "a b c + * d 5"
Đã đọc hết biểu thức Q, lần lượt lấy các phần tử cuối trong stack đặt vào P cho đến hết. P = "a b c + * d 5 ^ -".

5 Likes

ngôn ngữ gì cũng được chủ yếu xử lý thế nào thoi bạn

Tạo operandStack và operatorStack là stack rỗng.

Bước 1:
Đọc từ trái sang phải, tách các toán hạng (operand), toán tử (operator), dấu ngoặc mở ( và ngoặc đóng ). Tại mỗi bước thực hiện:

  • Nếu là operand, push vào operandStack
  • Nếu là + hoặc -, xử lý tất cả operator trong operatorStack thông qua pop, kết quả push vào operandStack
  • Nếu là * hoặc /, xử lý tất cả operator * / trong operatorStack thông qua pop, kết quả push vào operandStack
  • Nếu là (, push ( vào operatorStack
  • Nếu là ), xử lý tất cả operator cho đến khi operator ( được thấy thông qua peek.

Bước 2:
Nếu operandStack và operatorStack rỗng, thì tiếp tục xử lý tiếp.

P/s: giải thuật chưa xử lý edge cases.

Code
import java.util.Stack;

public class EvaluateExpression {
    public static void main(String[] args) {
        String expression = " 2*(5*10)+5-20/4";
        try {
            System.out.println(evaluateExpression(expression));
        } catch (Exception ex) {
            System.out.println("Wrong expression: " + expression);
        }
    }

    public static int evaluateExpression(String expression) {
        // Create operandStack to store operands
        Stack<Integer> operandStack = new Stack<>();

        // Create operatorStack to store operators
        Stack<Character> operatorStack = new Stack<>();

        // Insert blanks around (, ), +, -, / and *
        expression = insertBlanks(expression);

        // Extract operands and operators
        String[] tokens = expression.split(" ");

        // Phase 1: Scan tokens
        for (String token : tokens) {
            if (token.length() == 0) // Blank space
                continue; // Back to the while loop to extract the next token
            else if (token.charAt(0) == '+' || token.charAt(0) == '-') {
                // Process all +, -, *, / in the top of the operator stack
                while (
                    !operatorStack.isEmpty() && (
                        operatorStack.peek() == '+' ||
                        operatorStack.peek() == '-' ||
                        operatorStack.peek() == '*' ||
                        operatorStack.peek() == '/')) {
                    processOperator(operandStack, operatorStack);
                }

                // Push the + or - operator into the operator stack
                operatorStack.push(token.charAt(0));
            } else if (token.charAt(0) == '*' || token.charAt(0) == '/') {
                // Process all *, / in the top the operator stack
                while (
                    !operatorStack.isEmpty() && (
                        operatorStack.peek() == '*' ||
                        operatorStack.peek() == '/')) {
                    processOperator(operandStack, operatorStack);
                }

                // Push the * or / operator into the operator stack
                operatorStack.push(token.charAt(0));
            } else if (token.trim().charAt(0) == '(') {
                operatorStack.push('('); // Push '(' to stack'
            } else if (token.trim().charAt(0) == ')') {
                // Process all the operators in the stack until seeing '('
                while (operatorStack.peek() != '(') {
                    processOperator(operandStack, operatorStack);
                }

                operatorStack.pop(); // Pop the '(' symbol from the stack
            } else { // An operand scanned
                // Push an operand to the stack
                operandStack.push(new Integer(token));
            }
        }

        // Phase 2: Process all the remaining operators in the stack
        while (!operatorStack.isEmpty()) {
            processOperator(operandStack, operatorStack);
        }

        // Return the result
        return operandStack.pop();
    }

    /**
     * Process one operator: take an operator from operatorStack
     * and apply it on the operands in the operandStack
     */
    public static void processOperator(Stack<Integer> operandStack, Stack<Character> operatorStack) {
        char op = operatorStack.pop();
        int op1 = operandStack.pop();
        int op2 = operandStack.pop();

        if (op == '+')
            operandStack.push(op2 + op1);
        else if (op == '-')
            operandStack.push(op2 - op1);
        else if (op == '*')
            operandStack.push(op2 * op1);
        else if (op == '/')
            operandStack.push(op2 / op1);
    }

    public static String insertBlanks(String s) {
        String result = "";

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (
                c == '(' || c == ')' ||
                c == '+' || c == '-' ||
                c == '*' || c == '/') {
                result += " " + c  + " ";
            } else
                result += c;
        }

        return result;
    }
}
4 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?