JAVAデータ構造-スタックと中綴り表現、サフィックス表現が簡単計算機を実現します.

4119 ワード

JAVAデータ構造

先進的な後出のデータ構造、倉庫入、倉庫出、ポインタを常にスタックの一番上に向けて指定します.データがない場合は-1です.

1.配列シミュレーションを使ってスタック-構造を定義する

class ArrayStack {
    private int MaxSize;   //        
    private int[] array;    //         
    private int top = -1;    //    ,     -1     

    public ArrayStack(int maxSize) {        
        MaxSize = maxSize;
        array = new int[maxSize];
}}

2.スタックの方法
1.データがある場合topは0から開始します. だから top=maxSize-1の場合は満杯となります. 2.top=-1は空です
3.スタックに入るときは、トップを上に移動し、トップの位置にデータを追加します. 4.出庫時 topを下に移動します.データは実際にスタックから出ていません.topはスタックトップデータの変化を指します.
5.スタックを巡回する場合、スタックトップから巡回

    public Boolean isFull() {                 -1  ,  top 0  
        return top == MaxSize - 1;
    }

    public Boolean isEmpty() {       top=-1 ,   
        return top == -1;
    }

        ,   
    public void push(int num) {
        if (isFull()) {
            System.out.println("   ,    ~~");
            return;
        }
        top++;
        array[top] = num;        }

    *       ,   
    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("   ,    ~!");
        }
        int value = array[top];
        top--;
        return value;            }

二.中綴り表現とスタックの実現単純計算機
1.プレフィックス式 (3+4)×5-6対応するプレフィックス表現は、-× + 3 4 5 6
.右から左にスキャンする表式数字がスタックに入ると、符号が出ます. イジェクト二つの数字 number 1 number 2 使用 number 1 演算子 number 2
2.中式サフィックス表現はよくある演算式です.例えば、(3＋4)×5-6 人々はよく計算方法を使います.
3.拡張式 (3+4)×5-6対応の接尾辞表現は3 4+5です.× 6–
  .左から右へ式をスキャンします. 数字がスタックに入ると、符号が出ます. イジェクト二つの数字 number 1 number 2 使用 number 2 演算子 number 1
2.中式計算大体の考え
1.二つのスタックを用意する 1. データストア 2.符号スタックの保存
2.果が符号である場合: 1.符号スタックが空の場合または現在の記号の優先度が大きいスタックトップ記号の優先度直接倉庫に入れる
2.もし現在の記号の優先度は以下です. スタックトップ記号の優先度データスタックの2つの数字を取り出します. num 1, num 2 演算子を取り出します.
運をつける算を置く num 2 演算子 num 1, 演算結果をデータスタックに入力し、新しい記号をスタックに入れます.
3.最後にスキャン完了、順番二つのデータを取り出します演算子計算をして、結果をスタックに入れます.
データスタックに残した数字は最後の計算結果です.
式のような列  expression="3+2*3-1"
1.初めてスキャンするデータースタック 3,2,3です記号スタックは＋、* 2.-をスキャンすると、優先度が*より小さい   データスタックの二つの数字を取り出して計算します. そして、スタックに入ります
3.データスタック 3,6です ,1 記号スタックは＋です ,-
5.順次二つのデータを取り出します演算子計算をして、結果をスタックに入れます. 6.最終データスタックの数字は8です.
三.拡張式とスタックの実現単純計算機
1.拡張式は計算機の計算に適しています. 中缀の表式は更に人类の计算に适します. サフィックス表現も逆ポーランド式
2.次の通りです   中式   (30+4)*5-6 サフィックスに変換「30 4+5*6-」各文字をセットに入れます. [3,4,+,5,*,6,-]

public List getArrayList(String expression) {

        List expresList  = new ArrayList<>();

        String[] s = expression.split(" ");
        for (String s1 : s) {
            expresList.add(s1);
        }
        return expresList;   }

3.遍歴 [3,4,+,5,*,6,-] 計算します javaを使う提供するスタック
1.数字であれば直接倉庫に入れる 2.符号なら倉庫から二つの数字を取り出す. 現在の記号との計算そして結果をスタックに入れる 3.最終スタックに数字を残して結果とする

private int Calculator(List arrayList) {
        Stack stack = new Stack<>();
        for (String item : arrayList) {
            if (item.matches("\\d+")){
                stack.push(item);
            }else {
                int num1 = Integer.parseInt(stack.pop());
                int num2 = Integer.parseInt(stack.pop());
                int res= 0;
                if (item.equals("+")){
                    res=num2+num1;
                }else if (item.equals("-")){
                    res=num2-num1;
                }else if (item.equals("*")){
                    res=num2*num1;
                }else if (item.equals("/")){
                    res=num2/num1;
                }else {
                    throw new RuntimeException("    !");
                }
                stack.push(res+"");
            }}
        return Integer.parseInt(stack.pop());   }     29

コンカレントリンク