AOJ 1346: Miscalculation

問題

• 問題ページ: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1346
• ソースコード: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1359068
• 言語はJavaを使用

問題文訳

ボブは機械に強くない小学生である。 彼は父の計算機を見つけたので、ズルをしてそれで宿題を解こうとした。 彼の宿題は掛け算と足し算の式を解くことである。 掛け算は足し算よりも先に計算するのだが、計算機は演算子の優先順位を無視して単純に初めから計算してしまう。 このため、彼の出した答えには、以下の2通りのルールで計算したものが混在している。

1. 掛け算を足し算より先に行う
2. 左から右へ、演算子の優先順位を無視して行う

そこで、どちらの演算規則に基づいた答えであるか求めるプログラムを書きたい。

式には整数と演算子が含まれている。すべての整数は一桁（0以上9以下）である。 演算子には + と * の2種類があり、それぞれ足し算と掛け算を意味する。

例えば以下のような式があったとする

1+2*3+4

この式を、1のルールで計算すると、答えは11となる。 2のルールで計算すると、答えは13となる。

どちらのルールで計算しても同じ答えになることもある。 さらには、ボブは計算を間違えていることもある。

入力

入力は1つのテストケースにつき2行である。 最初の行には計算式が与えられる。 計算式はかならず奇数文字になり、その長さは17文字以下である。 奇数文字目には'0'以上9'以下の数字が、偶数文字目には'+'か'*'の演算が出現する。 二行目はボブの答えが0以上999999999以下で与えられる。

出力

出力はは以下の文字のいずれかである

M: 掛け算優先ルールで計算した答えである L: 左から右へ計算した答えである U: どちらのルールで計算してもボブが出した答えと同じ答えになる（どちらのルールでも同じ答えになる） I: どちらのルールで計算してもボブが出した答えにはならない（ボブが計算を間違えている）

解答

• 頑張って演算木を作って計算する。
• 左から右ルールは単純に前から見ていって計算する
• 掛け算優先ルールは、足し算が木の根本になるように、再起を使って計算する（コードを見たらわかりやすいかも）

演算木生成と計算クラスExpr

mに掛け算優先ルール, lに左から右ルールの結果が格納される

class Expr{
    String toString;
    char[] expr;
    int m, l;
    Expr(String str){
        toString = str;
        expr = str.toCharArray();
        
        m = multFirst(expr, 0, expr.length - 1);
        l = rightToLeft(expr);
    }
    
    /**
    * 左から右に計算していく
    */
    int rightToLeft(char[] expr){
        int ans = toInt(expr[0]);
        for(int i = 1; i < expr.length; i += 2){
            switch(expr[i]){
            case '+':
                ans += toInt(expr[i+1]);
                break;
            case '*':
                ans *= toInt(expr[i+1]);
                break;
            }
        }
        return ans;
    }
    
    int multFirst(char[] expr, int left, int right){
        if(left == right){
            return toInt(expr[left]);
        }
        
        // 足し算
        for(int i = left+1; i <= right; i += 2){
            if(expr[i] == '+'){
                return multFirst(expr, left, i-1) + multFirst(expr, i+1, right);
            }
        }
        
        // 足し算がなかったら掛け算を探す
        for(int i = left+1; i <= right; i += 2){
            if(expr[i] == '*'){
                return multFirst(expr, left, i-1) * multFirst(expr, i+1, right);
            }
        }
        
        return 0;
    }
    
    int toInt(char c){
        return c - '0';
    }
    
}

Mainメソッド

• ifの中身の順番だけ意識して、正しく場合分けできるようにすることだけ意識。

class Main extends MyUtil{
    // public static Graph g;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Expr e = new Expr(br.readLine());
        int a = Integer.parseInt(br.readLine());
        if(e.m == e.l && e.m == a){
            System.out.println("U");
        }else if(e.m == a){
            System.out.println("M");
        }else if(e.l == a){
            System.out.println("L");
        }else{
            System.out.println("I");
        }
    }
}