ホームページ >Java >&#&チュートリアル >ケーススタディ: 式の評価
スタックを使用して式を評価できます。スタックとキューには多くの用途があります。このセクションでは、スタックを使用して式を評価するアプリケーションについて説明します。以下の図に示すように、Google から算術式を入力して式を評価できます。
Google は式をどのように評価しますか?このセクションでは、複数の演算子と括弧を使用して 複合式 を評価するプログラムを示します (例: (15 + 2) * 34 – 2)。簡単にするために、オペランドは整数であり、演算子は +、-、**、および */.
この問題は、オペランドと演算子をそれぞれ格納するためのoperandStack と operatorStack という名前の 2 つのスタックを使用して解決できます。オペランドと演算子は、処理される前にスタックにプッシュされます。 オペレーターが処理されるとき、それは operatorStack からポップされ、operandStack の最初の 2 つのオペランドに適用されます (2 つのオペランドは operandStack)。結果の値は operandStack にプッシュバックされます。 アルゴリズムは 2 つのフェーズで進行します:
フェーズ 1: 式のスキャン
抽出された項目がオペランドの場合は、それを
operatorStack の先頭から演算子を繰り返し処理します。 下の表は、式 (1 + 2) * 4 - 3
.を評価するためにアルゴリズムがどのように適用されるかを示しています。
以下のコードはプログラムを示し、以下の図はサンプル出力を示しています。
本書で提供されている
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 に置き換えると、プログラムは機能します。 プログラムは、1 つの文字列内のコマンドライン引数として式を受け取ります。
evaluateExpression
メソッドは、operandStack と operatorStack という 2 つのスタックを作成し (24、27 行目)、スペースで区切られたオペランド、演算子、括弧を抽出します ( 30 ~ 33 行目)。 insertBlanks メソッドは、オペランド、演算子、括弧が少なくとも 1 つの空白で区切られるようにするために使用されます (行 30)。 プログラムは、for
ループ (行 36 ~ 72) で各トークンをスキャンします。トークンが空の場合はスキップします (行 38)。トークンがオペランドの場合は、それをoperandStack にプッシュします (70 行目)。トークンが + または – 演算子の場合 (39 行目)、operatorStack の先頭からすべての演算子を処理します (41 ~ 43 行目) 、新しくスキャンされたオペレーターをスタックにプッシュします (行 46)。トークンが ***** または / 演算子の場合 (48 行目)、operatorStack/ 演算子を処理します。 🎜> (存在する場合) (行 50 ~ 51)、新しくスキャンされたオペレーターをスタックにプッシュします (行 55)。トークンが ( 記号の場合 (57 行目)、operatorStack にプッシュします。トークンが ) 記号の場合 (60 行目)、) シンボル (行 62 ~ 64) が表示されるまで 🎜>operatorStack を実行し、スタックから ) シンボルをポップします。
すべてのトークンが考慮された後、プログラムは operatorStack 内の残りの演算子を処理します (75 ~ 77 行目)。
processAnOperator メソッド (84 ~ 96 行目) はオペレーターを処理します。このメソッドは、operatorStack から演算子をポップし (85 行目)、operandStack から 2 つのオペランドをポップします (86 ~ 87 行目)。演算子に応じて、メソッドは演算を実行し、演算の結果を operandStack にプッシュして戻します (89、91、93、95 行目)。
以上がケーススタディ: 式の評価の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。