AOJ0109 Smart Calculator

問題リンク Smart Calculator

• 解法

数式の構文解析問題です。
構文解析問題は1回解くことができれば他の問題でも十分応用できるかと思います。
問題文中にBNFがあればやりやすくなりますが、なければ自分で思い描くしかないです。
たぶん、この問題のような四則演算だと
式 ::= 式 "+" 式 | 式 "-" 式 | 項
項 ::= 要素 "*" 要素 | 要素 "/" 要素
要素 ::= "("式")" | "+"式 | "-"式 | [0-9]
みたいなノリのルールを作って、これを解析すればいいと思います。
解析文字列の先頭から順に見て行って、上記のどれに該当するかを調べます。
自分は基本的に上記のルールを全部メソッド化します。式ならexp(), 項ならterm(), 要素ならfact()みたいに。するとコーディングが楽になるんじゃないかと思います。頭の整理もできますし。

• ソース

import java.util.Scanner;

//Smart Calculator
public class AOJ0109 {

	static char[] s;
	static int id;
	
	static int exp(){
		int r = term();
		while(true){
			char c = s[id++];
			if(c=='+')r+=term();
			else if(c=='-')r-=term();
			else break;
		}
		return r;
	}
	
	static int term(){
		int r = fact();
		while(true){
			char c = s[id++];
			if(c=='*') r*=fact();
			else if(c=='/')r/=fact();
			else break;
		}
		id--;
		return r;
	}
	
	static int fact(){
		char c = s[id++];
		if(c=='(')return exp();
		if(c=='-'){
			return -fact();
		}
		if(c=='+'){
			return fact();
		}
		int x = c-'0';
		while(true){
			c = s[id++];
			if(Character.isDigit(c)){
				x *= 10;
				x += c-'0';
			}
			else break;
		}
		id--;
		return x;
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		while(t--!=0){
			s = sc.next().toCharArray();
			id = 0;
			System.out.println(exp());
		}
	}
}