Kajian Kes: Menilai Ungkapan

Tindanan boleh digunakan untuk menilai ungkapan. Tindanan dan baris gilir mempunyai banyak aplikasi. Bahagian ini memberikan aplikasi yang menggunakan tindanan untuk menilai ungkapan. Anda boleh memasukkan ungkapan aritmetik daripada Google untuk menilai ungkapan tersebut, seperti yang ditunjukkan dalam Rajah di bawah.

Bagaimanakah Google menilai ungkapan? Bahagian ini membentangkan atur cara yang menilai ungkapan majmuk dengan berbilang pengendali dan kurungan (cth., (15 + 2) * 34 – 2). Untuk kesederhanaan, anggap bahawa operan ialah integer dan pengendalinya terdiri daripada empat jenis: +, -, ** dan */.

Masalah ini boleh diselesaikan menggunakan dua tindanan, yang dinamakan operandStack dan operatorStack, masing-masing untuk menyimpan operan dan operator. Operand dan operator ditolak ke dalam tindanan sebelum ia diproses. Apabila operator diproses, ia muncul daripada operatorStack dan digunakan pada dua operan pertama daripada operandStack (dua operan muncul daripada operandStack). Nilai terhasil ditolak kembali ke operandStack.

Algoritma diteruskan dalam dua fasa:

Fasa 1: Mengimbas ungkapan

Atur cara mengimbas ungkapan dari kiri ke kanan untuk mengekstrak operan, operator dan kurungan.

1. Jika item yang diekstrak ialah operan, tolak ia ke operandStack.
2. Jika item yang diekstrak ialah pengendali + atau -, proses semua operator di bahagian atas operatorStack dan tolak operator yang diekstrak ke operatorStack.
3. Jika item yang diekstrak ialah operator ***** atau /, proseskan operator ***** atau / di bahagian atas operatorStack dan tolak operator yang diekstrak ke operatorStack.
4. Jika item yang diekstrak ialah simbol (, tolak ke operatorStack.
5. Jika item yang diekstrak ialah simbol ), proses operator berulang kali dari atas operatorStack sehingga melihat simbol ( pada tindanan.

Fasa 2: Membersihkan timbunan

Proses operator berulang kali dari bahagian atas operatorStack sehingga operatorStack kosong.

Jadual di bawah menunjukkan cara algoritma digunakan untuk menilai ungkapan (1 + 2) * 4 - 3.

Kod di bawah memberikan atur cara, dan Rajah di bawah menunjukkan beberapa sampel output.

package demo;
import java.util.Stack;

public class EvaluateExpression {

    public static void main(String[] args) {
        // Check number of arguments passed
        if(args.length != 1) {
            System.out.println("Usage: java EvaluateExpression \"expression\"");
            System.exit(1);
        }

        try {
            System.out.println(evaluateExpression(args[0]));
        }
        catch(Exception ex) {
            System.out.println("Wrong expression: " + args[0]);
        }
    }

    /** Evaluate an 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() == '/')) {
                    processAnOperator(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 of the operator stack
                while(!operatorStack.isEmpty() && (operatorStack.peek() == '*' || operatorStack.peek() == '/')) {
                    processAnOperator(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() != '(') {
                    processAnOperator(operandStack, operatorStack);
                }

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

        // Phase 2: Process all the remaining operators in the stack
        while(!operatorStack.isEmpty()) {
            processAnOperator(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 processAnOperator(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++) {
            if(s.charAt(i) == '(' || s.charAt(i) == ')' || s.charAt(i) == '+' || s.charAt(i) == '-' || s.charAt(i) == '*' || s.charAt(i) == '/')
                result += " " + s.charAt(i) + " ";
            else
                result += s.charAt(i);
        }

        return result;
    }

}

Anda boleh menggunakan kelas GenericStack yang disediakan oleh buku atau kelas java.util.Stack yang ditakrifkan dalam API Java untuk mencipta tindanan. Contoh ini menggunakan kelas java.util.Stack. Program ini akan berfungsi jika ia digantikan dengan GenericStack.

Atur cara mengambil ungkapan sebagai hujah baris perintah dalam satu rentetan.

Kaedah evaluateExpression mencipta dua tindanan, operandStack dan operatorStack (baris 24, 27), dan mengekstrak operan, operator dan kurungan (dibataskan oleh ruang baris 30–33). Kaedah insertBlanks digunakan untuk memastikan bahawa operan, operator dan kurungan dipisahkan oleh sekurang-kurangnya satu kosong (baris 30).

Atur cara mengimbas setiap token dalam gelung untuk (baris 36–72). Jika token kosong, langkau ia (baris 38). Jika token ialah operan, tolaknya ke operandStack (baris 70). Jika token ialah pengendali + atau – (baris 39), proses semua operator dari bahagian atas operatorStack, jika ada (baris 41–43) , dan tolak operator yang baru diimbas ke dalam tindanan (baris 46). Jika token ialah operator ***** atau / (baris 48), proses semua operator ***** dan / dari bahagian atas operatorStack, jika ada (baris 50–51), dan tolak operator yang baru diimbas ke tindanan (baris 55). Jika token ialah ( simbol (baris 57), tolaknya ke dalam operatorStack. Jika token ialah simbol ) (baris 60), proses semua operator dari bahagian atas operatorStack sehingga melihat simbol ) (baris 62–64) dan pop simbol ) daripada tindanan.

Selepas semua token dipertimbangkan, program memproses baki pengendali dalam operatorStack (baris 75–77).

Kaedah processAnOperator (baris 84–96) memproses operator. Kaedah ini mengeluarkan operator daripada operatorStack (baris 85) dan mengeluarkan dua operan daripada operandStack (baris 86–87). Bergantung pada operator, kaedah menjalankan operasi dan menolak hasil operasi kembali ke operandStack (baris 89, 91, 93, 95).

Atas ialah kandungan terperinci Kajian Kes: Menilai Ungkapan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!