Javaで文字列を数式に変換したい

Question

■
お世話になっております。

またしても学習サイトで分からない問題があったため質問させていただきたいです。

「String形式で書かれた数式の答えを求める関数を作成せよ
条件　引数、答えはすべてint型とする
例　引数　"(1 + 2 ) * 3"
答え　９　　　　　　　　　　　　　　　　　　　　　　　」

文字を列をCharacterに変換し、さらにisDigit()で数値かどうかを
判断すれば答えが求められるのでは、と考えたのですが
正しい答えは導き出せず、元の数式に戻っただけでした。

こちらはどのようにすれば数式として扱えるのでしょう。
(Characterの１をint型に変換するとUnicodeの関係で49となるところを
強引に変換している所も正直イマイチだと思ってはいます・・・。)

import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        
        strConversion("(1 + 2) * 3"); 
        
    }
    
    
    public static void strConversion(String str){
        String ans ="";
        
        for(int i = 0; i <= str.length() -1; i++){
            char X = str.charAt(i);
            if(Character.isDigit(X)){
                //数値
                ans += Integer.valueOf(X) -48;  //UniCode      
                System.out.println("数値:" + X);
            }else{
                //文字列
                ans += String.valueOf(X);
                System.out.println("文字:" + X);
            }
            
        }
        System.out.println(ans);
    }
}

追記
みなさま回答ありがとうございます。
私の想定より難易度が高かったようでせっかくの助言がなかなか理解出来ていません…。
頂いた回答をもとにもう少し理解を深めてからレスポンスさせていただきます。

※レスポンス、及び回答受付は一旦保留させていただきます。

Comments

[dodox86]

> こちらはどのようにすれば数式として扱えるのでしょう。

質問者さんはもしかすると課題の意図を取り違えているのではないか、と思うので、回答ではなくコメントのみです：

"(1 + 2 ) * 3"、この数式を文字列から自分で分解して カッコ、数値、+、*、などの加減乗除などの記号に分け、計算できるようにせよ、と言う問題なのではないでしょうか。

[tmp-user]

[文字列で書かれた演算式を計算する処理(関数)を作成してください

・文字列は 正の整数、半角スペース、半角括弧、演算子(+,-,*)のみで構成。
・計算結果はintの範囲を想定。]

という問題だったのでてっきり文字列から数値を取り出す、という事を考えたのですが、おっしゃるように演算子を発見する問題なのではという気もしてきました…。
この観点でも調べてみます。ありがとうございます。

[dodox86]

数式を使う課題の場合、コンピュータで扱いやすい「逆ポーランド記法」と言うものを使うことも多いのですが、そうではない一般的な数式だと少し難しいかもしれませんね。カッコが複数存在したりネストしていたりすることも想定すると結構面倒です。ネストされたカッコを考える場合、「再帰」を使うことを検討しても良いかもしれません。

[dodox86]

（私のコメント）
> ネストされたカッコを考える場合
あ、いえ、間違えました。一般的な加減乗除の計算式なのですから、中カッコも無く、カッコ閉じカッコ'()'がネストすることはないのでした。この点、大変失礼しました。

[jimbe]

実際に計算するようですね.
数式文字列→逆ポーランド化→計算と言う段階を経る感じでしょうか.

[jimbe]

> 私の想定より難易度が高かったようで
学習サイトがどのようなレベルの方を対象にこの問題を出しているのかが気になる所です.
「数値の桁数の制限も無く(負数もあり?)演算子の優先順位を考慮しかつ括弧ありでどれだけ長い式かも分からない」ということであれば, 少なくとも"文字列→数値変換をどうやるか考える"レベルの方向けでは無いと思います.
これが, 「式中の数字は正数1桁のみ(結果は負数や複数桁になる可能性あり?), 優先順位は考えず左から順に計算, 括弧無し, 演算子数は2個まで」...つまり "1 + 2 * 3" で 9 になるような問題であれば, まだ簡単かとは思いますが...

Answer 1

再帰下降構文解析でやってみました。

import java.io.*;

class Expr {
	char c;  int pos = 0, val = 0;  String str, o = "+-*/";

	Expr(String s) { str = s; }

	char get() {
		while (pos < str.length())
			if ((c = str.charAt(pos++)) != ' ' ) {
				if (!Character.isDigit(c)) return c;
				for (val = c - '0'; ; ) {
					if (pos == str.length()) return c ='0';
					c = str.charAt(pos++);
					if (!Character.isDigit(c)) { pos--; return c = '0'; }
					val = val * 10 + (c - '0');
				}
			}
		return c = 0;
	}

	int expr(int i) {
		int v;
		if (i < o.length())
			for (v = expr(i + 2); c == o.charAt(i) || c == o.charAt(i + 1); )
				if (c == '+') v += expr(i + 2);
				else if (c == '-') v -= expr(i + 2);
				else if (c == '*') v *= expr(i + 2);
				else v /= expr(i + 2);
		else
			if (get() == '0') { v = val; get(); }
			else if (c == '(') {
				v = expr(0);
				if (c == ')') get();
				else c = 2;
			}
			else if (c == '+') v = expr(i);
			else if (c == '-') v = -expr(i);
			else { v = 0; c = 1; }
		return v;
	}

	public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		for (;;) {
			System.out.print(">> ");
			String s = br.readLine();
			if (s.equals(".")) break;
			Expr e = new Expr(s);
			int v = e.expr(0);
			System.out.println(e.c == 0 ? " " + v : " Error");
		}
	}
}

バグのご指摘歓迎します。

追記
get の中の return '0'; を return c = '0'; に修正しました。

追記2
逆ポーランド記法に変換してからそれを評価するようにしてみました。

import java.util.*;

class Rpn {
	char c;  int pos = 0, len, val;  String str, o = "+-*/";
	StringBuilder sb = new StringBuilder();

	Rpn(String s) { str = s; len = s.length(); }

	char get() {
		while (pos < len) {
			c = str.charAt(pos++);
			if (c != ' ' ) {
				if (!Character.isDigit(c)) return c;
				for (val = c - '0'; ; ) {
					if (pos == len) return c = '0';
					c = str.charAt(pos++);
					if (!Character.isDigit(c)) { pos--; return c = '0'; }
					val = val * 10 + (c - '0');
				}
			}
		}
		return c = 0;
	}

	void put(Object o) { sb.append(' ').append(o); }

	void expr(int i) {
		if (i < 4)
			for (expr(i + 2); c == o.charAt(i) || c == o.charAt(i + 1); ) {
				char d = c; expr(i + 2); put(d);
			}
		else if (get() == '0') { put(val); get(); }
		else if (c == '(') { expr(0); if (c == ')') get(); else c = 2; }
		else if (c == '+') expr(i);
		else if (c == '-') { expr(i); put('_'); }
		else c = 1;
	}

	int eval(String rpn) {
		Scanner scn = new Scanner(rpn);
		Stack<Integer> s = new Stack<>();
		int v;
		for (;;)
			if (scn.hasNextInt())
				s.push(scn.nextInt());
			else if (scn.hasNext()) {
				String op = scn.next();
				if (op.equals("+")) s.push(s.pop() + s.pop());
				else if (op.equals("-")) s.push(-s.pop() + s.pop());
				else if (op.equals("*")) s.push(s.pop() * s.pop());
				else if (op.equals("/")) { v = s.pop(); s.push(s.pop() / v); }
				else if (op.equals("_")) s.push(-s.pop());
				else return 0;
			}
			else return s.pop();
	}

	public static void main(String[] args) throws Exception {
        Scanner scn = new Scanner(System.in);
		for (;;) {
			System.out.print(">> ");
			if (!scn.hasNextLine()) break;
			String s = scn.nextLine();
			if (s.equals(".")) break;
			Rpn rpn = new Rpn(s);
			rpn.expr(0);
			if (rpn.c == 0) {
				s = rpn.sb.toString();
				System.out.println(s + "  ==> " + rpn.eval(s));
			}
			else System.out.println(" Error"); 
		}
	}
}

new しているクラスは Scanner, Stack, StringBuilder だけです。
ラムダ式なんか使っていません。
理解できなくてもかまいませんが、どこが分からないかを教えていただけませんか？

追記3
計算を double で行うようにしてみました。

import java.util.Scanner;
import java.util.regex.*;

class Expr {
	String str;  int len, pos;  double val;
	char c, op[] = { '+', '-', '*', '/', '^', '^' };
	Pattern p = Pattern.compile("\d+\.?\d*([eE][+-]?\d+)?");

    Expr(String s) { str = s; len = s.length(); pos = 0; }

    char get() {
        while (pos < len)
            if ((c = str.charAt(pos++)) != ' ' ) {
                if (!Character.isDigit(c)) return c;
				String s = str.substring(--pos);
				Matcher m = p.matcher(s);
				m.find();
				s = m.group();
				val = Double.parseDouble(s);
				pos += s.length();
				return c = '0';
            }
        return c = 0;
    }

    double expr(int i) {
        double v;
        if (i < 6)
            for (v = expr(i+2); c == op[i] || c == op[i+1]; )
                if (c == '+') v += expr(i+2);
                else if (c == '-') v -= expr(i+2);
                else if (c == '*') v *= expr(i+2);
                else if (c == '/') v /= expr(i+2);
				else v = Math.pow(v, expr(i));
        else if (get() == '0') { v = val; get(); }
		else if (c == '(') { v = expr(0); if (c == ')') get(); else c = 2; }
		else if (c == '+') v = expr(i);
		else if (c == '-') v = -expr(i);
		else if (str.startsWith("sqrt(", pos-1)) { pos += 3; v = Math.sqrt(expr(i)); }
		else v = c = 1;
        return v;
    }

    public static void main(String[] args) {
        for (Scanner scn = new Scanner(System.in); ; ) {
            System.out.print(">> ");
            if (!scn.hasNextLine()) break;
			String s = scn.nextLine();
            if (s.equals(".")) break;
            Expr e = new Expr(s);
            double v = e.expr(0);
            System.out.println(e.c == 0 ? " " + v : " Error");
        }
    }
}

べき乗演算子 ^ や関数 sqrt を追加しています。

実行例

>> 1+2*(3-4)/5
 0.6
>> 355/113
 3.1415929203539825
>> sqrt(2)
 1.4142135623730951
>> (1 + sqrt(5)) / 2
 1.618033988749895
>> sqrt(3^2 + 4^2)
 5.0
>> 2^3^2
 512.0
>> .

^ は右結合なので 2^(3^2) となります。

Comments

[xebme]

字句解析しているし、再帰によって優先度もうまく処理されていて、良いコードだと思います。

Answer 2

逆ポーランド記法を利用した計算

逆ポーランド記法を参考に、解析と計算を一度に実行するコードを書いてみました。

  static int eval(String expression) {
    Stack<Integer> operands = new Stack<>();
    Stack<Character> operators = new Stack<>();
    for (char c : expression.toCharArray()) {
      switch (c) {
      case ' ':
	break;
      case '(':
	operators.push(c);
	break;
      case ')':
	while (!operators.isEmpty()) {
	  char operator = operators.pop();
	  if (operator == '(') {
	    break;
	  }
	  operands.push(calculate(operands.pop(), operands.pop(), operator));
	}
	break;
      case '0':
      case '1':
      case '2':
      case '3':
      case '4':
      case '5':
      case '6':
      case '7':
      case '8':
      case '9':
	operands.push(c - '0');
	break;
      case '+':
      case '-':
      case '*':
	if (!operators.isEmpty() && precede(operators.peek(), c)) {
	  operands.push(calculate(operands.pop(), operands.pop(), operators.pop()));
	}
	operators.push(c);
	break;
      default:
	throw new RuntimeException("Invalid token : '" + c + "'");
      }
    }
    while (!operators.isEmpty()) {
      operands.push(calculate(operands.pop(), operands.pop(), operators.pop()));
    }
    return operands.pop();
  }

  static int calculate(int y, int x, char operator) {
    int result = 0;
    switch (operator) {
    case '+':
      result = x + y;
      break;
    case '-':
      result = x - y;
      break;
    case '*':
      result = x * y;
      break;
    }
    return result;
  }

  static int priority(char operator) {
    return (operator == '*') ? 2 : (operator == '(') ? 0 : 1;
  }

  static boolean precede(char op1, char op2) {
    return priority(op1) >= priority(op2);
  }

バグがあれば遠慮なく指摘してください。

参考

• 逆ポーランド記法
• 操車場アルゴリズム
• Parsing/RPN calculator algorithm
• Parsing/Shunting-yard algorithm

逆ポーランド記法（追記）

上のコードからcalculate()メソッドを削除しオペランドスタックをリストにかえてリストへ演算子を追加すると、逆ポーランド記法を生成できます。せっかくだから、逆ポーランド記法を生成して評価する関数型コードを書いてみました。

演算に除算/を追加して優先度を以下のように決定。

static Function<Character,Integer> priority = 
  operator -> (operator == '*' || operator == '/') ? 2
            : (operator == '+' || operator == '-') ? 1 : 0;
  
static BiFunction<Character,Character,Boolean> preceding = 
  (op1,op2) -> priority.apply(op1) >= priority.apply(op2);

逆ポーランド記法の生成器（関数）を定義する。逆ポーランド記法として出力されるのはList<Character>。

static Function<String,List<Character>> toRpn = expression -> {
  Deque<Character> operators = new LinkedList<>(); // キャプチャされる。
  List<Character> rpnList = expression.chars()
    .mapToObj(c -> Character.valueOf((char) c))
    .collect(
      ArrayList::new, 
      (accList, token) -> {
        switch (token) {
          case ' ':
            break;
          case '(':
            operators.push(token);
            break;
          case ')':
            while (!operators.isEmpty()) {
              char operator = operators.pop();
              if (operator == '(') {
                break;
              }
              accList.add(operator);
            }
            break;
          case '0':
          case '1':
          case '2':
          case '3':
          case '4':
          case '5':
          case '6':
          case '7':
          case '8':
          case '9':
            accList.add(token);
            break;
          case '+':
          case '-':
          case '*'
          case '/':
            if (!operators.isEmpty() && preceding.apply(operators.peek(), token)) {
              accList.add(operators.pop());
            }
            operators.push(token);
            break;
          default: // 
            throw new RuntimeException("Invalid token : '" + token + "' in '" + expression + "'");
        }
      }, 
      List::addAll);
  while (!operators.isEmpty()) {
    rpnList.add(operators.pop());
  }
  return rpnList;
};

逆ポーランド記法の評価

上で作成したList<Character>を入力する逆ポーランド記法の評価器（関数）を定義。

static Function<List<Character>,Integer> evalRpn = rpn -> {
  Deque<Integer> result = 
    rpn.stream()
       .collect(
          LinkedList::new,
          (operandStack, token) -> {
            switch (token) {
              case '0':
              case '1':
              case '2':
              case '3':
              case '4':
              case '5':
              case '6':
              case '7':
              case '8':
              case '9':
                operandStack.push(token - '0');
                break;
              case '+':
                operandStack.push(operandStack.pop() + operandStack.pop());
                break;
              case '-':
                operandStack.push(-operandStack.pop() + operandStack.pop());
                break;
              case '*':
                operandStack.push(operandStack.pop() * operandStack.pop());
                break;
              case '/':
                operandStack.push((int)(1d / operandStack.pop() * operandStack.pop()));
                break;
            }
          }, 
         Deque::addAll);
  return result.pop();
 };

逆ポーランド記法の生成と評価を合成。

static Function<String,Integer> eval = toRpn.andThen(evalRpn);

利用方法。

String expression = "2 * (1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9)";
int result = eval.apply(expression);
System.out.println(expression + " = " + result);

Answer 3

こちらを参考に↓
Java 再帰下降構文解析 超入門