『アルゴリズム4』——全左括弧の問題を補う

タイトル
『アルゴリズム』の授業後の問題を完成する過程で、一つの問題の内容は以下の通りである.

      ，                                  。  ，    ：
1 + 2 ) * 3 - 4 ) * 5 - 6 ) ) )
        ：
((1 + 2) * ((3 - 4) * (5 - 6)))

構想
この問題は四則表現を求める問題、いわゆるダブルスタック法に似ているような気がします.ダブルスタック法の原理は以下の通りである.

1.     Stack，         (optrStack)    (dataStack).
2.      ，      ，      ；      ，         optrStack         ：            ，      。            ，      ，  dataStack       ，            。
3.   2，  optrStack    。

このテーマは、デュアルスタック法を参照して実現できます.

我々は、2つのStack、オペレータスタック(optrStack)、およびオペランドスタック(dataStack)を構築する.

式を遍歴し、右かっこでなければオペレータかどうかを判断し、はいはoptrStack、いいえはdataStackに入る.右かっこの場合は、optrStackとdataStackをそれぞれスタックから出し、「(」+d 1+opt+d 2+")」の式を作成してからdataStackに入れればよい.

リファレンスコード

import java.util.Stack;

/** * Created by wzy on 16-1-17. */
public class CompleteParentese {

    private String completeParentese(String str) {
        Stack<String> optrStack = new Stack<>();
        Stack<String> dataStack = new Stack<>();

        for (int i = 0; i < str.length(); i++) {
            if (isDigit(str.charAt(i))) {
                //        
                dataStack.push(String.valueOf(str.charAt(i)));
            } else if (isOpeartor(str.charAt(i))) {
                //         
                optrStack.push(String.valueOf(str.charAt(i)));
            } else {
                //         
                String d2 = dataStack.pop();
                String d1 = dataStack.pop();
                String opt = optrStack.pop();
                String exstr = "(" + d1 + opt + d2 + ")";
                dataStack.push(exstr);
            }
        }

        while (optrStack.size() > 0) {
            String opt = optrStack.pop();
            String d2 = dataStack.pop();
            String d1 = dataStack.pop();
            String exstr = "(" + d1 + opt + d2 + ")";
            dataStack.push(exstr);
        }

        return dataStack.pop();
    }

    private boolean isOpeartor(char ch) {
        return ch == '+' || ch == '-' || ch == '*' || ch == '/';
    }

    private boolean isDigit(char ch) {
        return ch >= '0' && ch <= '9';
    }

    public static void main(String[] args) {
        String str = "1+2)*3-4)*5-6)))";
        CompleteParentese cp = new CompleteParentese();
        String res = cp.completeParentese(str);
        System.out.println(res);
    }
}

上記のコードは、スペースなどの特殊文字を考慮せずに、関連コードを自分で追加することができます.