사례 연구: 표현식 평가

스택을 사용하여 표현식을 평가할 수 있습니다. 스택과 큐에는 많은 응용 프로그램이 있습니다. 이 섹션에서는 스택을 사용하여 표현식을 평가하는 애플리케이션을 제공합니다. 아래 그림과 같이 Google에서 산술 표현식을 입력하여 표현식을 평가할 수 있습니다.

Google은 표현식을 어떻게 평가하나요? 이 섹션에서는 여러 연산자와 괄호(예: (15 + 2) * 34 – 2)를 사용하여 복합 표현식을 평가하는 프로그램을 제공합니다. 단순화를 위해 피연산자는 정수이고 연산자는 +, -, ** 및 */.

피연산자와 연산자를 각각 저장하기 위해

operandStack 및 operatorStack이라는 두 개의 스택을 사용하여 문제를 해결할 수 있습니다. 피연산자와 연산자는 처리되기 전에 스택에 푸시됩니다. 연산자가 처리되면 operandStack에서 팝되고 operandStack의 처음 두 피연산자에 적용됩니다(두 피연산자는 operandStack). 결과 값은 operandStack으로 다시 푸시됩니다. 알고리즘은 두 단계로 진행됩니다.

1단계: 표현식 스캔

프로그램은 표현식을 왼쪽에서 오른쪽으로 스캔하여 피연산자, 연산자 및 괄호를 추출합니다.

추출된 항목이 피연산자이면

operandStack
1. 에 푸시합니다. 추출된 항목이
+
2. 또는 - 연산자인 경우 operatorStack 상단의 연산자를 모두 처리하고 추출된 연산자를 에 푸시합니다. 연산자스택. 추출된 항목이 ***** 또는
/
3. 연산자인 경우 operatorStack/ 연산자를 처리합니다. > 추출된 연산자를 operatorStack으로 푸시합니다. 추출된 항목이 (
기호인 경우
4. operatorStack에 푸시합니다. 추출된 항목이 )
기호인 경우 스택에서
5. ( 기호가 나타날 때까지 operatorStack의 최상위부터 연산자를 반복적으로 처리합니다. 2단계: 스택 지우기

operatorStack

이 비어 있을 때까지

operatorStack의 최상위부터 연산자를 반복적으로 처리합니다. 아래 표는 (1 + 2) * 4 - 3

.

표현식을 평가하기 위해 알고리즘이 어떻게 적용되는지 보여줍니다.

아래 코드는 프로그램을 제공하고 아래 그림은 일부 샘플 출력을 보여줍니다.

스택 생성에는 책에서 제공하는

GenericStack

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

}

클래스나 Java API에 정의된

java.util.Stack 클래스를 사용할 수 있습니다. 이 예에서는 java.util.Stack 클래스를 사용합니다. GenericStack으로 대체하면 프로그램이 작동합니다. 프로그램은 하나의 문자열에서 표현식을 명령줄 인수로 사용합니다.

evaluateExpression

메서드는 두 개의 스택,

operandStack 및 operatorStack(24, 27행)을 생성하고 공백으로 구분된 피연산자, 연산자 및 괄호를 추출합니다( 30~33행). insertBlanks 메소드는 피연산자, 연산자 및 괄호가 하나 이상의 공백(30행)으로 구분되도록 하는 데 사용됩니다. 프로그램은 for

루프(36~72행)에서 각 토큰을 검색합니다. 토큰이 비어 있으면 건너뜁니다(38행). 토큰이 피연산자인 경우

operandStack(70행)에 푸시합니다. 토큰이 + 또는 – 연산자(39행)인 경우 operatorStack 상단의 모든 연산자를 처리합니다(있는 경우)(41~43행). , 새로 스캔된 연산자를 스택에 푸시합니다(라인 46). 토큰이 ***** 또는 / 연산자(라인 48)인 경우 operatorStack/ 연산자를 처리합니다. 🎜> 있는 경우(라인 50-51), 새로 검색된 연산자를 스택에 푸시합니다(라인 55). 토큰이 ( 기호(57행)인 경우 operatorStack에 푸시합니다. 토큰이 ) 기호(60행)인 경우 operatorStack ) 기호(62-64행)가 보일 때까지 스택에서 ) 기호를 팝합니다.

모든 토큰을 고려한 후 프로그램은 operatorStack(75~77행)의 나머지 연산자를 처리합니다.

processAnOperator 메서드(84~96행)는 연산자를 처리합니다. 이 메서드는 operatorStack(85행)에서 연산자를 팝하고 operandStack(86~87행)에서 두 개의 피연산자를 팝합니다. 연산자에 따라 메서드는 작업을 수행하고 작업 결과를 operandStack(89, 91, 93, 95행)으로 다시 푸시합니다.

위 내용은 사례 연구: 표현식 평가의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!