編集履歴

回答編集履歴

コメントの回答追加

2016/10/20 17:17

投稿

スコア1105

answer CHANGED Viewed

@@ -1,138 +1,415 @@
-演算子の優先順位が同じで、( )を使わない、電卓のような場合は比較的単純に修正できます。
 ```Java
 import java.io.BufferedReader;
 import java.io.InputStreamReader;
+import java.util.ArrayDeque;
+import java.util.EmptyStackException;
+import java.util.HashMap;
+import java.util.Stack;
 import java.util.StringTokenizer;
 // Calcクラス
-public class Calc {
+public class Calc
+{
 	// メインメソッド
-	public static void main(String[] args) {
+	public static void main(String[] args)
+	{
-		try {
+		try
-			int ans = 0;
+		{
 			InputStreamReader isr = new InputStreamReader(System.in);
+			BufferedReader bReader = new BufferedReader(isr);
-			BufferedReader br = new BufferedReader(isr);
 			Calc calc = new Calc();
+			for (; ;)
+			{
-			for (String expr = br.readLine();
+				// プロンプトの出力
-				 expr != null && ! expr.equals("");
+				System.out.print(">");
-				 expr = br.readLine()) {
+				String expr = bReader.readLine();
+				if (expr == null || expr.equals(""))
+				{
+					break;
+				}
-				try {
+				try
+				{
-					ans = calc.calc(expr);
+					int ans = calc.calc(expr);
 					System.out.println("=" + ans);
 				}
-				catch (UsrExprException e) {
+				catch (UsrExprException e)
+				{
 					System.out.println("式に誤りがあります : " + e.getMessage());
 				}
 			}
-		}
+		}
-		catch (Exception e) {
+		catch (Exception e)
+		{
+			System.out.println("例外 : " + e);
+		}
-			System.out.println("例外："+ e);
+		System.out.println("終了");
-		}
 	}
-	public int calc(String expr) throws Exception {
+	public int calc(String expr) throws Exception
+	{
-		int ans = 0;
+		// 全ての空白文字を取り除く
+		expr = expr.replaceAll("\\s+", "");
+		boolean printRevPolishExpr = false;
+		// p で始まっていたら、逆ポーランド記法表示モード
-		StringTokenizer tokenizer = new StringTokenizer(expr, "+-*/", true);
+		if (expr.startsWith("p"))
+		{
+			printRevPolishExpr = true;
+			expr = expr.substring(1);
+		}
-		String sign = "+";
+		// 字句解析
-		String operator = "+";
+		StringTokenizer tokenizer = new StringTokenizer(expr, "+-/*", true);
-		while (tokenizer.hasMoreTokens()) {
+		ArrayDeque<String> tokenQueue = new ArrayDeque<>();
+		while (tokenizer.hasMoreTokens())
+		{
-			String token = tokenizer.nextToken().trim();
+			String token = tokenizer.nextToken();
-			if (token.length() == 0) {
+			if (! token.isEmpty())
+			{
+				tokenQueue.add(token);
+			}
+		}
+		tokenQueue = replaceAsUnaryOps(tokenQueue);
+		ArrayDeque<String> revPolishQueue = toRevPolish(tokenQueue);
+		if (printRevPolishExpr)
+		{
+			ArrayDeque<String> revPolishExpr = revPolishQueue.clone();
+			while (! revPolishExpr.isEmpty())
+			{
+				System.out.print(" " + revPolishExpr.remove());
+			}
+			System.out.println();
+		}
+		return evaluate(revPolishQueue);
+	}
+	// 単項演算子を見つけて置換する
+	protected static ArrayDeque<String> replaceAsUnaryOps(ArrayDeque<String> tokenQueue)
+	{
+		ArrayDeque<String> outQueue = new ArrayDeque<>();
+		// 前回の演算子を"+"に初期化
+		String lastOperator = "+";
+		while (! tokenQueue.isEmpty())
+		{
+			String token = tokenQueue.remove();
+			if (isNumber(token))
+			{
+				lastOperator = null;
+				outQueue.add(token);
 				continue;
 			}
-			int num;
+			// tokenは演算子
-			if (! token.matches("[-+*/]")) {
+			if (lastOperator == null)
+			{
+				lastOperator = token;
+				outQueue.add(token);
+				continue;
+			}
-				// トークンが演算子でなければ、整数と解釈し、演算を行う
+			// 前回も演算子
-				try {
-					num = Integer.parseInt(token);
-				}
-				catch (NumberFormatException e) {
+			switch (token)
+			{
-					throw new UsrExprException("整数ではない");
+			case "+":
+				// 何もしないので詰めない
-				}
+				break;
+			case "-":
-				if (sign.equals("-")) {
+				if (lastOperator.equals("u-"))
-					num = - num;
-				}
+				{
+					// 2回連続"u-"である場合
-				if (operator.equals("+")) {
+					// 前回詰めた"u-"を捨てる
+					outQueue.removeLast();
+					// 前々回詰めた演算子を復元する
+					lastOperator = outQueue.peekLast();
-					ans += num;
+					if (lastOperator == null)
+					{
+						// 前回の演算子を"+"に再初期化
+						lastOperator = "+";
+					}
 				}
+				else
+				{
-				else if (operator.equals("-")) {
+					lastOperator = "u-";
-					ans -= num;
+					outQueue.add("u-");
 				}
-				else if (operator.equals("*")) {
+				break;
+			default:
-					ans *= num;
+				lastOperator = token;
+				outQueue.add(token);
-				}
+			}
-				else if (operator.equals("/")) {
+		}
-					ans /= num;
+		return outQueue;
-				}
+	}
+	// 式を逆ポーランド記法に変換する
+	protected  static ArrayDeque<String> toRevPolish(ArrayDeque<String> tokenQueue)
+			throws UsrExprException
+	{
+		ArrayDeque<String> outQueue = new ArrayDeque<>();
+		Stack<String> stack = new Stack<>();
+		while (! tokenQueue.isEmpty())
+		{
+			String token = tokenQueue.remove();
+			if (isNumber(token))
+			{
+				// 数値ならば無条件にキューに書き出す
-				operator = null;
+				outQueue.add(token);
+				continue;
 			}
-			else {
-				// トークンが演算子の場合
-				if (operator == null) {
+			// tokenは演算子
+			if (stack.isEmpty())
+			{
-					// 前回が演算子でなければ、演算子を保存
+				// スタックが空ならば無条件にスタックに積む
-					operator = token;
+				stack.push(token);
+				continue;
+			}
-					// 符号に + をセット
+			// スタックは空ではない
-					sign = "+";
-				}
-				else {
-					// 前回が演算子の場合
+			// tokenの優先順位を得る
+			int priorityOfToken = getPriorityOf(token);
+			// スタックの先頭を得る(ただし取り出さない)
+			String topOfStack = stack.peek();
-					if (token.equals("-") || token.equals("+")) {
+			if (priorityOfToken > getPriorityOf(topOfStack))
+			{
+				// スタックの先頭より優先順位が高ければスタックに積む
+				stack.push(token);
+				continue;
+			}
+			do
+			{
-						// トークンが符号であれば、演算子はそのまま
+				// スタックの先頭を取り出してキューに書き出す
-						// 符号にトークンをセット
+				topOfStack = stack.pop();
-						sign = token;
+				outQueue.add(topOfStack);
-					}
-					else {
+				// スタックの先頭より優先順位が低くなるまで繰り返す
-						throw new UsrExprException("演算子の次が符号でない");
+				if (priorityOfToken > getPriorityOf(topOfStack))
-					}
+				{
+					break;
 				}
 			}
+			while (! stack.isEmpty());
+			// スタックに積む
+			stack.push(token);
 		}
-		// 式の最後に整数がない場合
+		// スタックに残っている全てを取り出してキューに書き出す
-		if (operator != null) {
+		while (! stack.isEmpty())
+		{
+			String topOfStack = stack.pop();
+			outQueue.add(topOfStack);
+		}
+		return outQueue;
+	}
-			throw new UsrExprException("式の最後に整数がない");
+	protected static boolean isNumber(String token)
+	{
+		try
+		{
+			Integer.parseInt(token);
+			return true;
 		}
+		catch (NumberFormatException e)
+		{
+			return false;
+		}
+	}
+	// 演算子の優先順位を定義
+	protected static final HashMap<String, Integer> priorityMap =
+		new HashMap<String, Integer>() {
+		{
+			// ※数値が高いほど、優先順位が高いとする
+			put("u+", 3); // 単項演算子
+			put("u-", 3); // 単項演算子
+			put("*", 2);
+			put("/", 2);
+			put("+", 1);
+			put("-", 1);
+		}
+	};
+	// 演算子の優先順位を得る
+	protected static int getPriorityOf(String operator)
+			throws UsrExprException
+	{
+		Integer priority = priorityMap.get(operator);
+		// 見つからない場合はnullを返す
+		if (priority != null)
+		{
+			return priority;
+		}
+		throw new UsrExprException("'" + operator + "':未知の演算子");
+	}
+	// 逆ポーランド記法に変換された式を評価する
+	protected static int evaluate(ArrayDeque<String> revPolishQueue)
+			throws UsrExprException
+	{
+		int ans;
+		ValueStack stack = new ValueStack();
+		try
+		{
+			while (! revPolishQueue.isEmpty())
+			{
+				String token = revPolishQueue.remove();
+				if (isNumber(token))
+				{
+					// 数値ならば無条件にスタックに積む
+					stack.push(token);
+					continue;
+				}
+				int operand1;
+				int operand2;
+				switch (token)
+				{
+				case "u+": // 単項 + 演算子
+					// スタックはそのまま
+					break;
+				case "u-": // 単項 - 演算子
+					operand1 = stack.pop();
+					// 演算結果をスタックに積む
+					stack.push(- operand1);
+					break;
+				case "+":
+					operand2 = stack.pop();
+					operand1 = stack.pop();
+					// 演算結果をスタックに積む
+					stack.push(operand1 + operand2);
+					break;
+				case "-":
+					operand2 = stack.pop();
+					operand1 = stack.pop();
+					// 演算結果をスタックに積む
+					stack.push(operand1 - operand2);
+					break;
+				case "*":
+					operand2 = stack.pop();
+					operand1 = stack.pop();
+					// 演算結果をスタックに積む
+					stack.push(operand1 * operand2);
+					break;
+				case "/":
+					operand2 = stack.pop();
+					operand1 = stack.pop();
+					// 演算結果をスタックに積む
+					stack.push(operand1 / operand2);
+					break;
+				}
+			}
+			// 最終結果をスタックから取り出す
+			ans = stack.pop();
+		}
+		catch (EmptyStackException e)
+		{
+			throw new UsrExprException("数値が足りない");
+		}
+		if (! stack.empty())
+		{
+			throw new UsrExprException("演算子が足りない");
+		}
-		//ansを返す
+		// ansを返す
 		return ans;
 	}
 }
+import java.util.EmptyStackException;
+import java.util.Stack;
+public class ValueStack {
+	private Stack<Integer> stack = new Stack<>();
+	public ValueStack() {
+	}
+	public int push(int item) {
+		return stack.push(item);
+	}
+	public int push(String item) throws NumberFormatException {
+		Integer num = Integer.parseInt(item);
+		if (num == null)  {
+			throw new NullPointerException();
+		}
+		return stack.push(num);
+	}
+	public int pop() throws EmptyStackException {
+		return stack.pop();
+	}
+	public boolean empty() {
+		return stack.empty();
+	}
+}
 ```
-優先順位や( )を考慮する場合は、根本的な修正が必要です。
+キュー、スタックはデータ構造で、よく使われます。
+case 文字列: … break;　はJavaのバージョンによって使えない場合があります。
-その場合、式を逆ポーランド記法へ変換してから、演算を行うと簡単でしょう。
+else if (token.equals(文字列)) { … } に変えてください。
-逆ポーランド記法への変換アルゴリズムも知られているので、調べてください。
+逆ポーランド記法に変換するメソッドを少し変えるだけで( )も扱えるようになります。
+優先順位を正しく設定すると、Javaのほかの演算子、%, &, |, ^, ~などにも対応できます。
+字句解析を正規表現によるマッチングに変えると、浮動小数点、複数文字の演算子、>>, >>>, <<やJavaにはない演算子、例えばべき乗 ** も扱えるようになりますね。