計算機の機能追加に関する質問

Question

javaで計算機のプログラムを作成しました。
単項マイナス演算(例、-10+5)を行う処理を追加したいのですが
修正方法がわかりません。
どのように修正したらよいでしょうか？
今後の参考の為にどなたか教えてください
よろしくお願いします。

また下記のソースコードで改正案があればご教授願います。
よろしくお願いします。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class UsrExprException extends Exception {
	
        public UsrExprException(String s){
		super(s);
	}
}
//Calcクラス
public class Calc {
	//メインメソッド
	public static void main(String[] args) {
		
		try {
			int ans = 0;      
			
			InputStreamReader isr = new InputStreamReader(System.in);
			
			BufferedReader br = new BufferedReader(isr);
			
	        String s = br.readLine();
			
			while (s != null && !s.equals("")) {
		
				Calc calc = new Calc();
				
				ans = calc.calc(s);
	
				System.out.println("=" + ans);
				
				s = br.readLine()
			}
			
		} catch (Exception  e) {
		
			System.out.println("例外："+ e);
		}
	}

	public int calc(String s) throws UsrExprException {
		
		UsrExprException ue;
	
		int ans = 0;

		StringTokenizer st = new StringTokenizer(s, "+-*/", true);
		
		String sign = "+";
		
		String tok ;
		int tknum = 0;
		
		while (st.hasMoreTokens()) {
         
			tok = st.nextToken();
			
			tok = tok.trim();
            
			if (tok.length() == 0) {
			
				continue;
			}
			
			if (tknum % 2 == 0) {
				
				if (sign.equals("+")) {
					
					ans += Integer.parseInt(tok);
				}  
				else if (sign.equals("-")) {
					ans -= Integer.parseInt(tok);
				}  
				else if (sign.equals("*")) {
					ans *= Integer.parseInt(tok);
				}  
				else if (sign.equals("/")) {
					ans /= Integer.parseInt(tok);
				}
			} else {
				   
					sign = tok;
			}
			
			tknum++;
		}
		//式の最後が整数でない場合
		if ( tknum % 2 == 0) {
				ue = new UsrExprException("最終整数なし");
				throw ue;
		}
		//ansを返す
		return ans;
	}
}

```

Comments

[KSwordOfHaste]

質問編集時に入力エリアの上の方にある「</>」を使ってコードを見やすく整形しないとインデンテーションがつかないので閲覧者にみずらいコードになってしまいますよ。

[ikedas]

チラ見なので間違ってるかもしれませんが、今のプログラムは「電卓」っぽい動きをしてるようです。つまり、1.記号キーで計算の種類が決まり、2.被演算数を記憶し、3.計算して結果出力。このやり方でいくのか、それとももっと複雑な式 (たとえば1+2×3で2×3を先に計算するとか、括弧が使えるとか) が計算できるものにしたいのでしょうか。どちらですか。

[Oracle]

このやり方での修正をを希望です。

Answer 1

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 static void main(String[] args)
	{
		try
		{
			InputStreamReader isr = new InputStreamReader(System.in);
			BufferedReader bReader = new BufferedReader(isr);

			Calc calc = new Calc();

			for (; ;)
			{
				// プロンプトの出力
				System.out.print(">");

				String expr = bReader.readLine();
				if (expr == null || expr.equals(""))
				{
					break;
				}

				try
				{
					int ans = calc.calc(expr);
					System.out.println("=" + ans);
				}
				catch (UsrExprException e)
				{
					System.out.println("式に誤りがあります : " + e.getMessage());
				}
			}
		}
		catch (Exception e)
		{
			System.out.println("例外 : " + e);
		}

		System.out.println("終了");
	}


	public int calc(String expr) throws Exception
	{
		// 全ての空白文字を取り除く
		expr = expr.replaceAll("\\s+", "");

		boolean printRevPolishExpr = false;
		// p で始まっていたら、逆ポーランド記法表示モード
		if (expr.startsWith("p"))
		{
			printRevPolishExpr = true;
			expr = expr.substring(1);
		}

		// 字句解析
		StringTokenizer tokenizer = new StringTokenizer(expr, "+-/*", true);

		ArrayDeque<String> tokenQueue = new ArrayDeque<>();

		while (tokenizer.hasMoreTokens())
		{
			String token = tokenizer.nextToken();

			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;
			}

			// tokenは演算子

			if (lastOperator == null)
			{
				lastOperator = token;
				outQueue.add(token);
				continue;
			}

			// 前回も演算子

			switch (token)
			{
			case "+":
				// 何もしないので詰めない
				break;

			case "-":
				if (lastOperator.equals("u-"))
				{
					// 2回連続"u-"である場合

					// 前回詰めた"u-"を捨てる
					outQueue.removeLast();

					// 前々回詰めた演算子を復元する
					lastOperator = outQueue.peekLast();
					if (lastOperator == null)
					{
						// 前回の演算子を"+"に再初期化
						lastOperator = "+";
					}
				}
				else
				{
					lastOperator = "u-";
					outQueue.add("u-");
				}
				break;

			default:
				lastOperator = token;
				outQueue.add(token);
			}
		}

		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))
			{
				// 数値ならば無条件にキューに書き出す
				outQueue.add(token);
				continue;
			}

			// tokenは演算子

			if (stack.isEmpty())
			{
				// スタックが空ならば無条件にスタックに積む
				stack.push(token);
				continue;
			}

			// スタックは空ではない

			// tokenの優先順位を得る
			int priorityOfToken = getPriorityOf(token);

			// スタックの先頭を得る(ただし取り出さない)
			String topOfStack = stack.peek();
			if (priorityOfToken > getPriorityOf(topOfStack))
			{
				// スタックの先頭より優先順位が高ければスタックに積む
				stack.push(token);
				continue;
			}

			do
			{
				// スタックの先頭を取り出してキューに書き出す
				topOfStack = stack.pop();
				outQueue.add(topOfStack);

				// スタックの先頭より優先順位が低くなるまで繰り返す
				if (priorityOfToken > getPriorityOf(topOfStack))
				{
					break;
				}
			}
			while (! stack.isEmpty());

			// スタックに積む
			stack.push(token);
		}

		// スタックに残っている全てを取り出してキューに書き出す
		while (! stack.isEmpty())
		{
			String topOfStack = stack.pop();
			outQueue.add(topOfStack);
		}

		return outQueue;
	}

	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を返す
		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にはない演算子、例えばべき乗 ** も扱えるようになりますね。

Comments

[Oracle]

回答ありがとうございます。
一つお聞きしたいのですが、トークンが演算子の場合
何のために符号"+"をセットしているのでしょうか？

また、 下記の処理の説明も併せてご説明を伺いたいのですが。
どうかよろしくお願い致します。
if (sign.equals("-")) {
num = - num;
}

[naomi3]

符号を再初期化するためです。
sign = "-" のときに、次に符号"-"が来ないにもかかわらず、自動的に負数になることを避けるためです。signにセットするのはnullまたは"-"以外であれば何でもいいです。

[naomi3]

単項演算子(-)の処理です。
整数の前に"-"があれば、負数にします。

[Oracle]

naomi3さん。
丁寧なご回答ありがとうございます。
大変ご参考になりました。

[Oracle]

申し訳ございませんが、再度ご質問させて下さい。
上記のコードの場合、2*--2と入力した場合、結果は答えの4ではない-4と出力されてしまいます。
おそらくマイナス単項演算の処理ができていないことが原因だと思います。
このバグ処理を修正したいのですがどうすればいいでしょうか？
どうか宜しくお願いします

[naomi3]

public int calc(String expr) throws Exception {

int ans = 0;

StringTokenizer tokenizer = new StringTokenizer(expr, "+-*/", true);

// 符号を 正 に初期化
int sign = 1;

String operator = "+";

while (tokenizer.hasMoreTokens()) {

String token = tokenizer.nextToken().trim();

if (token.length() == 0) {

continue;
}

int num;

if (! token.matches("[-+*/]")) {

// トークンが演算子でなければ、整数と解釈し、演算を行う
try {
num = Integer.parseInt(token);
}
catch (NumberFormatException e) {

throw new UsrExprException("整数ではない");
}

// num の符号を sign に合わせる
num *= sign;

if (operator.equals("+")) {

ans += num;
}
else if (operator.equals("-")) {

ans -= num;
}
else if (operator.equals("*")) {

ans *= num;
}
else if (operator.equals("/")) {

ans /= num;
}

operator = null;
}
else {
// トークンが演算子の場合

if (operator == null) {

// 前回が演算子でなければ、演算子を保存
operator = token;

// 符号を 正 にリセット
sign = 1;
}
else {

// 前回が演算子の場合

if (token.equals("-") || token.equals("+")) {

// トークンが符号であれば、演算子はそのまま
// マイナスならば符号反転
sign *= (token.equals("-") ? -1 : 1);
}
else {

throw new UsrExprException("演算子の次が符号でない");
}
}
}
}

// 式の最後に整数がない場合
if (operator != null) {

throw new UsrExprException("式の最後に整数がない");
}

//ansを返す
return ans;
}

符号反転を簡単にするためにsignをintにしました。

[Oracle]

naomi3 さん。
度々のご回答ありがとうございます。
お詳しいですね。
ロジック周りは調べてもわからないところが
あるので非常に助かっております。

[Oracle]

naomi3 さん。
さっそくまた、質問させて下さい(笑)
上記の計算機の機能はそのままで
今度は1+4+3×5のような処理を行い、適切な答えが
返ってくる計算機のプログラムを作成したいと考えております。
ソースコードはおそらく大幅な修正が必要だと思います。
これは難しいとは思いますが
可能であればその処理ができるソースコード(上記のソースコードの修正)を記入
していただきたいのですがお願いできますでしょうか?
度々すみませんが、どうかよろしくお願いします。

Answer 2

よく目にする一般的な数式の場合、単項演算子(-)は２項演算子(+,-,,/)より優先度が高いというのを利用して再帰下降構文解析という手法を使うとよいと思います。単項演算子だけでなく括弧による優先順の変更や'','/'を'+','-'よりも優先度を高くしたいといったことの実現にもうまくはまります。

「再帰下降構文解析」のキーワードでいくつかヒットすると思いますのでご自分が書いているコードと照らし合わせ、手頃なコード例が載っているサイトを探してみるとよいと思います。

追記：

優先順位ありの計算機をつくりたいとのことなので（再帰を使わなくても達成できますが）簡単な再帰下降構文解析の例を書いてみます。エッセンスを示すだけなので細かな処理は端折ります。数式の計算だと構文規則が割合単純なため演算子の優先順に従い直感的に書けます。(すみませんが動かしてないのでバグあったらゴメンナサイ)

// この方法ではトークンを１つ先読みできることが前提なのでこういうTokenizerがあると思ってください
// 簡単のために最後に必ず'='などの式の終わりを示すトークンがあると仮定します。
class Tokenizer extends StringTokenizer {
  string currentToken;

  string nextToken() {
    string result = currentToken;
    currentToken = nextToken();
    return result;
  }
}

class Calculation {
  // ここが計算の入り口です
  int evalExpression(Tokenizer t) {
    t.nextToken(); // 常に１個だけトークンを先読みしておく。以降全て同じ
    return additiveExpression(t);
  }

  // 加減算の式の計算:'+'や'-'がある限り計算します
  int additiveExpression(Tokenizer t) {
    int result = multiplicativeExpression(t);
    for (;;) {
      switch (t.currentToken) {
      case "+":
        t.nextToken();
        result += multiplicativeExpression(t);
        break;
      case "-":
        t.nextToken();
        result -= multiplicativeExpression(t);
        break;
      case "=":
        return result;
      default:
        throw new RuntimeException("syntax error");
    }
  }

  // 乗除算の式の計算:'*'や'/'がある限り計算します
  int multiplicativeExpression(Tokenizer t) {
    int result = unaryExpression(t);
    for (;;) {
      switch (t.currentToken) {
      case "*":
        t.nextToken();
        result *= unaryExpression(t);
        break;
      case "/":
        t.nextToken();
        result /= unaryExpression(t);
        break;
      default:
        return result;
    }
  }

  // 単項演算子、括弧、または数字の計算
  int unaryExpression(Tokenizer t) {
    switch (t.currentToken) {
      case "-":
        t.nextToken();
        return -unaryExpression(t);
      case "(": {
        t.nextToken();
        int result = additiveExpression(t);
        if (!t.currentToken.equals(")")
          throw new RuntimeException("syntax error");
        t.nextToken();
        return result;
      }
      default: {
        int result = Integer.parseInt(t.currentToken);
        t.nextToken();
        return result;
      }
    }
  }
}

Comments

[Oracle]

素晴らしいですね。
ご回答ありかとうございます。
大変参考になりました。

[KSwordOfHaste]

単に一つの例として挙げましたが、再帰を使わないアルゴリズムやスタックを使ったものとかも含めてアルゴリズムを考える幅が広がると思うので時間がゆるすならいろいろやってみるとよいと自分は思います。

Answer 3

ご質問のコードでは、toknumという変数を見て「偶数個のトークンを受け取ったらsignに記憶しておいた計算をする」となっています。しかし考えてみると、変数signには常に「次にやる計算」が記憶されているのですから、何番目のトークンかを数えなくてもいいですね。

Calc.calc()をこんなふうに変えてみます。

    public int calc(String s) throws UsrExprException {
        UsrExprException ue;

        int ans = 0;         // アキュムレータ。初期値は0。
        String sign = "ADD"; // 内部状態。初期状態は"ADD"。

        StringTokenizer st = new StringTokenizer(s, "+-*/", true);
        String tok ;

        while (st.hasMoreTokens()) {
            tok = st.nextToken();
            tok = tok.trim();

            if (tok.length() == 0) {
                continue;
            }

            if (tok.equals("+")) {
                // 処理なし。常に内部状態を"ADD"に更新
                sign = "ADD";
            }
            else if (tok.equals("-")) {
                // 処理なし。常に内部状態を"SUB"に更新
                sign = "SUB";
            }
            else if (tok.equals("*")) {
                // 処理なし。常に内部状態を"MUL"に更新
                sign = "MUL";
            }
            else if (tok.equals("/")) {
                // 処理なし。常に内部状態を"DIV"に更新
                sign = "DIV";
            }
            else { // トークンが数のとき
                // 内部状態によって決まる処理をする
                if (sign.equals("ADD")) {
                    ans += Integer.parseInt(tok);
                }  
                else if (sign.equals("SUB")) {
                    ans -= Integer.parseInt(tok);
                }  
                else if (sign.equals("MUL")) {
                    ans *= Integer.parseInt(tok);
                }  
                else if (sign.equals("DIV")) {
                    ans /= Integer.parseInt(tok);
                }
                else {
                    ue = new UsrExprException("最終整数なし");
                    throw ue;
                }
                // 内部状態をリセット。
                sign = "";
            }
        }
        //ansを返す
        return ans;
    }

変数signは、次に何の計算をするかを記憶しています。つまり、プログラムの「内部状態」を表していると考えられます (トークンと内部状態の区別がつくよう、signの取る値を変えてみました)。

変更後のコードでは、

1. トークンをひとつづつ読み取って、
2. トークンの種類と現在の内部状態の組み合わせから実行すべき処理を決め、実行し、
3. さらに、同じ組み合わせから次の内部状態を決め、更新する。

という動作をしています。

このように、入力と内部状態に基づいて決められた動作をするものを決定性有限オートマトン (DFA) と呼び、コンピュータシステムのいろんなところで使われています (現実の電卓にも使われています)。DFAの考えかたを使うと、入力とそれに対する処理の関係がうまく整理できるので、機能拡張もやりやすくなります。

Comments

[Oracle]

丁寧な回答ありがとうございます。
大変ご参考になりました。