Java プログラミングスキル - データ構造とアルゴリズム「プレフィックス、インフィックス、サフィックス」

[[387421]]

接頭辞表現（ポーランド語表記）

プレフィックス式はポーランド式とも呼ばれます。プレフィックス式の演算子は演算子の前に置かれます。たとえば、(3+4)*5-6に対応するプレフィックス式は - * + 3 4 5 6 です。

コンピュータによる前置表現の評価

式を右から左にスキャンします。数値に遭遇すると、スタックにプッシュされます。演算子に遭遇すると、スタックの一番上の 2 つの数値がポップアウトされ、演算子を使用してそれら (一番上の要素と 2 番目に上の要素) に対応する計算が実行され、結果がスタックにプッシュされます。上記のプロセスを式の左端まで繰り返し、最後の計算で得られた値が式の結果になります。

たとえば、(3+4)*5-6 に対応するプレフィックス式は - * + 3 4 5 6 です。プレフィックス式を評価する手順は次のとおりです。

右から左にスキャンし、6、5、4、3 をスタックにプッシュします。
+ 演算子に遭遇すると、3 と 4 がポップされ (3 はスタックの一番上の要素、4 は 2 番目に上の要素)、3+4 の値が計算され、7 が取得され、7 がスタックにプッシュされます。
次に * 演算子が来るので、7 と 5 がポップされ、35 が計算され、35 がスタックにプッシュされます。
最後に、- 演算子は 35-6 の値、つまり 29 を計算し、これが最終結果となります。

中置表現

中置式は、(3*4)+5-6 のような一般的な算術式です。中置式の評価は人間にとって最も馴染み深いものですが、コンピュータにとっては操作が難しいため、結果を計算する際には中置式を他の式に変換して演算することがよくあります (通常は後置式に変換されます)。

接尾辞表現

逆ポーランド記法とも呼ばれる後置式は、演算子がオペランドの後に来る点を除いて、前置式に似ています。

例えば、(3+4)*5-6に対応する接尾辞式は3 4 + 5 * 6 -

例えば

接尾辞表現のコンピュータ評価

式を左から右にスキャンします。数値に遭遇したら、その数値をスタックにプッシュします。演算子に遭遇したら、スタックの一番上の 2 つの要素をポップし、演算子を使用してそれら (一番上の要素と 2 番目に上の要素) に対応する計算を実行し、結果をスタックにプッシュします。右端が表されるまで、上記のプロセスを繰り返します。最後の計算によって得られた値が式の結果です。

たとえば、(3+4)*5-6 に対応するサフィックス式は 3 4 + 5 * 6 - です。サフィックス式を評価する手順は次のとおりです。

左から右にスキャンして、3 と 4 をスタックにプッシュします。
+ 演算子に遭遇すると、4 と 3 がポップされ (4 はスタックの一番上の要素、3 は 2 番目に上の要素)、7 が計算され、7 がスタックにプッシュされます。
スタックに 5 をプッシュします。
* 演算子に遭遇すると、5 と 7 が取り出され、35 が計算され、35 がスタックにプッシュされます。
6 をスタックにプッシュします。
最後に、- 演算子は 29 を計算し、最終結果を返します。

中置式を後置式に変換する

1. 空の中間結果を格納するための演算子スタック s1 とスタック s2 の 2 つのスタックを初期化します。

2. 式を左から右にスキャンします。

3. オペランドが見つかったら、それを s2 にプッシュします。

4. 演算子に遭遇すると、その優先順位を s1 の最上位の演算子と比較します。

s1 が空の場合、またはスタックの一番上の演算子が左括弧 "(" の場合、演算子はスタックに直接プッシュされます。
それ以外の場合、優先順位がスタックの一番上の演算子よりも高い場合は、その演算子も s1 にプッシュされます。
それ以外の場合は、s1のスタックの一番上の演算子をポップしてs2にプッシュし、再び(4.1)に戻ってs1の新しい一番上の演算子と比較します。

5. 括弧に遭遇したとき:

左括弧「(」の場合は、直接 s1 にプッシュされます。
右括弧 ")" の場合、左括弧が検出されるまで、s1 のスタックの先頭にある演算子が 1 つずつポップアウトされ、s2 にプッシュされます。左括弧が検出されると、括弧のペアは破棄されます。

6. 式が右端に達するまで手順 2 ～ 5 を繰り返します。

7. s1 の残りの演算子をポップし、1 つずつ s2 にプッシュします。

8. s2 の要素を 1 つずつ取り出して出力します。結果の逆順が、中置式に対応する後置式になります。

シンプルな接尾辞式計算機

パッケージ com.structures.stack; 
 
 java.util.ArrayList をインポートします。
 java.util.Arrays をインポートします。
 java.util.List をインポートします。
 java.util.Stack をインポートします。 
 
パブリッククラス PolandNotation {
公共 静的void main(String[] args) {
        //まず逆ポーランド語表現を与えます (3+4)*5-6==>3 4 + 5 * 6 -
        文字列式 = "1+(((2+3)*4))-5" ;
        リスト<文字列> toInfixExpressionList = toInfixExpressionList(式);
        System.out.println (toInfixExpressionList) ;
        リスト<文字列> suffixExpressList = parseSuffixExpressList(toInfixExpressionList);
        System.out.println (サフィックスExpressList) ;
        System.out.println (calculate(suffixExpressList)) ;
        /*
        [1, +, (, (, (, 2, +, 3, ), *, 4, ), ), -, 5]
        演算子が存在しません
        演算子が存在しません
        [1、2、3、+、4、*、+、5、-]
        16
        */
    } 
 
    // 中置式に対応するリストを後置式に対応するリストに変換します
公共 静的リスト<String> parseSuffixExpressList(リスト<String> ls) {
        //2つのスタックを定義する
        Stack<String> s1 = new Stack<>(); //シンボルスタック
 
        //説明: スタック s2 は変換プロセス全体でポップ操作を行わないため、後で元に戻す必要があります。
        // そのため面倒です。ここでは Stack<String> ではなく、List<String> s2 を直接使用します。
        //Stack<String> s2 = new Stack<>(); //中間結果を格納するスタック s2
        リスト<文字列> s2 = 新しいArrayList<>();
 for (文字列項目: ls) {
            if (item.matches( "\\d+" )) {
                s2.add (アイテム);
            }そうでない場合、(item.equals( "(" )) {
                s1.push( "(" );
            }そうでない場合 (item.equals( ")" )) {
                //右括弧の場合)" 、 s1 のスタックの先頭にある演算子が 1 つずつポップアウトされ、左括弧が検出されるまで s2 にプッシュされます。左括弧が検出されると、括弧のペアは破棄されます。
                while (!s1.peek().equals( "(" )) {
                    s2 を追加します(s1 をポップします)。
                }
                s1.ポップ();
            }それ以外{
                // 項目の優先度がトップ演算子以下の場合、s1のトップ演算子をポップしてs2にプッシュし、再び(4.1)に戻ってs1の新しいトップ演算子と比較します。
                ( s1.size () != 0 && Operation.getValue(s1.peek()) >= Operation.getValue(item)) {
                    s2 を追加します(s1 をポップします)。
                }
                //アイテムをスタックにプッシュする必要もあります
                s1.push(アイテム);
            }
        }
        // s1 の残りの演算子をポップアウトして s2 にプッシュします
        ( s1.size () != 0 ) の間 {
            s2 を追加します(s1 をポップします)。
        }
 s2を返します。
    } 
 
    // 中置式をリストに変換する
公共 静的リスト<String> toInfixExpressionList(String s) {
        リスト<String> ls = 新しいArrayList<>(); 
 
整数i = 0;
        String str; //複数の数字を連結する
文字c;
        する {
            //cが数値でない場合は、lsを直接追加します
            ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) < 57) の場合 {
                ls.add ( "" + c);
                私は++;
            }それ以外{
                // 数値の場合は複数桁の問題を考慮する必要があります。
                str = "" ;
                (i < s.length() && (c = s.charAt(i)) >= 48 && (c = s.charAt(i)) <= 57) の場合 {
                    str + = c;
                    私は++;
                }
            }
        } while (i < s.length());
 lsを返します。
    } 
 
    //逆ポーランド記法に従って評価する
公共 静的  int計算(リスト<String> ls) {
        Stack<String> スタック = new Stack<>();
 for (文字列項目: ls) {
            //ここでは正規表現を使用して複数桁の数字を抽出します
            if (item.matches( "\\d+" )) {
                スタックにアイテムをプッシュします。
            }それ以外{
 int num2 = Integer.parseInt (stack.pop());
 int num1 = Integer.parseInt (stack.pop());
整数res = 0;
                スイッチ (アイテム) {
場合  「+」 :
                        数値1と数値2
                        壊す;
場合  「-」 ：
                        数値1 - 数値2;
                        壊す;
場合  「*」 :
                        数値1と数値2を合計します。
                        壊す;
場合  「/」 :
                        数値1/数値2;
                        壊す;
デフォルト：
                        新しい RuntimeException( "演算子エラー" ) をスローします。
                }
                スタックをプッシュします(res + "" );
            }
        }
戻る 整数.parseInt(stack.pop());
    }
 } 
 
 //演算子に応じて対応する優先順位番号を返す
クラス操作{
    プライベートスタティック 整数 追加= 1;
    プライベートスタティック  SUB = 1 ;
    プライベートスタティック 整数MUL = 2;
    プライベートスタティック 整数DIV = 2; 
 
公共 静的  int getValue(文字列操作) {
 int結果 = 0;
        スイッチ（操作）{
場合  「+」 :
                結果 = ADD ;
                壊す;
場合  「-」 ：
                結果 = SUB;
                壊す;
場合  「*」 :
                結果 = MUL;
                壊す;
場合  「/」 :
                結果 = DIV;
                壊す;
デフォルト：
                System.out.println ( "この演算子は存在しません" );
                壊す;
        }
結果を返します。
    }
 }