《计算方(第四版)》习题:1.3.9左かっこを补う

に質問
標準入力から左かっこが欠けている式を得て、カッコを補完した後の中順序式を印刷するプログラムを作成します.たとえば、指定された入力:1+2)*3-4)*5-6))あなたのプログラムは出力すべきです:((1+2)*((3-4)*(5-6))
構想
Dijkstraが発明した「ダブルスタック法」を採用することができる.

操作数を操作数スタックに圧入する.

演算子を演算子スタックに押し込む.

左かっこは無視されます.

右括弧に遭遇した場合、演算子がポップアップされ、必要な数のオペランドがポップアップされ、予算結果がオペランドスタックに押し込まれます.『アルゴリズム(第4版)』P 128

より抜粋
ダブルスタック分析:

操作数と演算子を分類し、異なるスタックに圧入する.

左かっこは無視されます.

右括弧を一つの標識とし、右括弧に出会うたびにデータをポップアップし、処理を行う.

ここでの処理は、数値を計算することであってもよいし、本題で文字列をリンク処理した後、処理結果をオペランドスタックに押し込むなどの他の処理方法であってもよい.

本題の考え方:

入力した数字と記号をスペースで区切って、文字列を1つずつ読み出す.

数字に出会ったらオペランドスタックに圧入し、演算子に出会ったら演算子スタックに圧入する.

右括弧に遭遇すると、2つのオペランドと1つの演算子がポップアップされ、文字列リンクが行われ、1つの文字列(全体)としてオペランドスタックに再押し込まれます.

スタック内のコンテンツは逆であるため、文字列リンクおよび最終出力結果の両方に追加処理が必要であり、具体的にはコードを参照してください.

コード:

package execise.chapter1_3;

import edu.princeton.cs.algs4.Stack;
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

/**
 * Created by Blue on 2016/7/3.
 *                                   ；
 *   ： 1 + 2 ） * 3 - 4 ） * 5 - 6 ） ） ）
 *   ： (（ 1 + 2 ） * (（ 3 - 4 ） * （ 5 - 6 ） ） ）
 */
public class E9 {

    public static void main(String[] args) {

        Stack ops = new Stack<>();  //    
        Stack vals = new Stack<>(); //    ,       ,      String,  double;

        while (!StdIn.isEmpty()) {
            String s = StdIn.readString();  //      ，    ，     ；

            if (s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/"))
                ops.push(s);
            else if (s.equals(")")) {
                //   ，      “）”、“（”，  “（”、“）”；
                String expre = ")" + vals.pop() + ops.pop() + vals.pop() + "(";

                //   ，           ，            ；
                vals.push(expre);
            } else
                vals.push(s);
        }

        String result = vals.pop();
        // output: result: )))6-5(*)4-3((*)2+1((
        StdOut.println("result: " + result);

        //        
        String seq = "";
        for (int i = result.length()-1; i >= 0; i--){
            seq += result.charAt(i);
        }

        // output: seq: ((1+2)*((3-4)*(5-6)))
        StdOut.println("seq: " + seq);

    }
}

参考リンクの小さいコラム