Java言語で、標準入力から受け取った数式を四則演算の原則に則って計算したい。

Question

Java言語で、標準入力から受け取った数式を四則演算の原則に則って計算したい。

ここに実現したいことを箇条書きで書いてください。

• 標準入力からString型の数式を受け取って(2×3+1、とか、100×50/20、(20+30)×5、2(3+5)/4みたいな、=はつかない、×や÷が来たら乗算・除算にする)それを四則演算の原則に則って計算(*や/は+や-に優先する、とか、()内の計算が優先とか)したいです。

↑上の文章で乗算を表そうとしてアスタリスクを書くと表示されないので×としています。

前提

開発環境はeclipse、OSはwindows11、ちなみにiniファイルを編集して文字コードをUTF-8にしました。

私のJavaスキル→勉強し始めて2週間たたない程度。変数宣言、算術演算子、if文での条件分岐、forやwhileなどの繰り返し処理、メソッドの使い方、クラスを分けての開発の仕方などを学びました。
ちなみに、独学ですがPHPは約1年、Pythonは半年ほど勉強しており、基本的な文法は抑えており、PHPはスクラッチで各種バリデーションやログイン機能を備えたアプリを開発したり、Laravelを用いて簡単なアプリを開発したことがあり、PythonはフレームワークにStreamlit、ライブラリにpandasやnumpy、altairなどを使っての簡単なwebアプリ開発の経験があります。

発生している問題・エラーメッセージ

特に何か問題が発生しているわけではなく、この問題を解くための手順だったり、考え方に関してご教授いただけたらなと思います。
私としては、①標準入力で受け取った数式をsplitなどで1文字ずつ分割して配列に格納、②*, /, +, -, (, )以外の値をint型に変換、③配列の値をループで回してint型の要素が連続したら数値を連結、*や/が来たら優先して計算、()も優先して計算、みたいな感じの流れでコードを書こうと思っているのですが、こちら実現したいことの欄でも述べたように、どうすれば四則演算の原則に従いつつうまくコードを書けるのかが分かりません(ライブラリなどを使えば簡単に書けるのかもしれませんが、あくまで私がこれまで学習した変数宣言、算術演算子、if文での条件分岐、forやwhileなどの繰り返し処理、メソッドの使い方、クラスを分けての開発などの知識のみで実装したいです。

該当のソースコード

まだ配列に格納するところまでしか実装しておりません。
この後の流れとしてどのように実装すればよいのか、またそもそも配列に1文字ずつ格納するやり方は効率的かどうかをご教授いただきたいです。

package chukan_kadai;

import java.util.Scanner;

public class chukan_kadai {
	public static void main(String args[]) {
　　　　　　System.out.println("数式を入力してください");
		
　　　　　　Scanner scanner = new Scanner(System.in);
　　　　　　String formula = scanner.nextLine();
		
　　　　　　String[] formulaArray = formula.split("");
	}
}

Comments

[Zuishin]

二週間でやるような課題じゃありませんが、テキストを間違えていませんか？
自信があるのであれば「逆ポーランド記法」を調べてみましょう。

[takayuki1107]

いえ、こちらテキストなどではなく、あるYouTube動画の講義です。
やはりこちら難易度高いですよね笑、安心しました。
逆ポーランド記法ですね、調べてみます。
コメントいただきありがとうございます。

[jimbe]

具体的なコードの問題で無いのでしたら、QA でなく意見交換にした方が良いのではないでしょうか。

Answer 1

字句解析、構文解析をして構文木を作り、構文木を評価して結果を出すのが一般的な手順です。
コンパイラ作成に関する書籍を読んだり、上記キーワードを調べてみてください。

四則演算に関しては、構文木を作らずにスタックを使って上手くやる方法もあります。

またそもそも配列に1文字ずつ格納するやり方

String#charAt() で一文字ずつアクセスできるので、配列にする必要はありません。

Comments

[takayuki1107]

ご回答ありがとうございます。
キーワードについてしっかり理解し実装を頑張ります。
改めてご回答ありがとうございます。

[takayuki1107]

ちなみになんですが、おすすめの書籍はございますでしょうか。

[int32_t]

おすすめの情報は持ち合わせていません。
昔『コンパイラ― 原理・技法・ツール』を読んでわかり難かった記憶があります。

本当にコンパイラを作りたいのではない限り、コンパイラの専門書よりはいろいろなアルゴリズムが載っている本で字句解析構文解析についても触れているもののほうがよいでしょうね。

[takayuki1107]

かしこまりました。ありがとうございます。

Answer 2

ざっくり RPN です。
enum 使っちゃってますが。

import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Main {
  public static void main(String[] args) {
    String[] testdata = { "1+2.5*-3", "100*50/20", "(20+30)*5", "2(3+5)/4" };
    for(String formula : testdata) {
      RPN rpn = new RPN(formula);
      System.out.println(rpn + "=" + rpn.calc());
    }
  }

  private static class RPN {
    private interface Element {
      void operate(Deque<String> stack);
    }

    private static class Value implements Element {
      private final String v;
      Value(String v) {
        this.v = v;
      }
      @Override
      public void operate(Deque<String> stack) {
        stack.push(v);
      }
      @Override
      public String toString() {
        return v;
      }
    }

    private enum Operator implements Element {
      PLS("+",1) { @Override protected double calc(double a, double b) { return a + b; } },
      MIN("-",1) { @Override protected double calc(double a, double b) { return a - b; } },
      MUL("*",2) { @Override protected double calc(double a, double b) { return a * b; } },
      DIV("/",2) { @Override protected double calc(double a, double b) { return a / b; } },
      BS("(",0),
      BE(")",0);

      private final String text;
      private final int pri;
      Operator(String text, int pri) {
        this.text = text;
        this.pri = pri;
      }

      static Operator of(char c) {
        for(Operator ope : values()) if(ope.text.charAt(0) == c) return ope;
        return null;
      }

      @Override
      public void operate(Deque<String> stack) {
        double b = Double.parseDouble(stack.pop());
        double a = Double.parseDouble(stack.pop());
        stack.push("" + calc(a, b));
      }

      protected double calc(double a, double b) {
        throw new UnsupportedOperationException();
      }

      @Override
      public String toString() {
        return text;
      }
    }

    private static class Translator {
      private static class Source {
        private static Pattern NUM_PATTERN = Pattern.compile("-?\\d+(:?\\.\\d+)?");

        private final String formula;
        private int index;

        Source(String formula) {
          this.formula = formula;
        }

        boolean isEnd() { return index >= formula.length(); }
        char getChar() { return formula.charAt(index); }
        Operator nextOperator() {
          Operator op = Operator.of(formula.charAt(index++));
          if(op == null) throw new IllegalArgumentException("Operator Error: index=" + index);
          return op;
        }
        Value nextNumber() {
          Matcher m = NUM_PATTERN.matcher(formula.substring(index));
          if(!m.find() || m.start() != 0) throw new IllegalArgumentException("Number Error: index=" + index);
          index += m.group().length();
          return new Value(m.group());
        }
      }

      private static class Destination {
        private Deque<Operator> stack = new ArrayDeque<>();
        private List<Element> list = new ArrayList<>();

        void put(Operator op) {
          if(op == Operator.BE) {
            while(!stack.isEmpty() && (op=stack.pop()) != Operator.BS) list.add(op);
            if(op != Operator.BS) throw new IllegalStateException("Formula Error: Unmatched parentheses.");
            return;
          }
          if(op != Operator.BS) {
            while(!stack.isEmpty() && stack.peek().pri >= op.pri) list.add(stack.pop());
          }
          stack.push(op);
        }
        void put(Value v) {
          list.add(v);
        }
        List<Element> complete() {
          while(!stack.isEmpty()) list.add(stack.pop());
          return new ArrayList<>(list);
        }
      }

      private enum Mode {
        NUM {
          Mode translate(Source src, Destination dst) {
            if(src.getChar() == '(') {
              dst.put(src.nextOperator());
              return this;
            }
            dst.put(src.nextNumber());
            return OP;
          }
        },
        OP {
          Mode translate(Source src, Destination dst) {
            Operator op = src.nextOperator();
            if(op == Operator.BE) {
              dst.put(op);
              return this;
            }
            if(op == Operator.BS) dst.put(Operator.MUL);
            dst.put(op);
            return NUM;
          }
        };

        abstract Mode translate(Source src, Destination dst);
      }

      static List<Element> translate(String formula) {
        Mode mode = Mode.NUM;
        Source src = new Source(formula);
        Destination dst = new Destination();
        while(!src.isEnd()) mode = mode.translate(src, dst);
        return dst.complete();
      }
    }

    private final String formula;
    private List<Element> list;

    RPN(String formula) {
      this.formula = formula;
      list = Translator.translate(formula);
    }

    String calc() {
      Deque<String> stack = new ArrayDeque<>();
      for(Element elm : list) elm.operate(stack);
      return stack.pop();
    }

    @Override
    public String toString() {
      return formula + "=" + list;
    }
  }
}

1+2.5*-3=[1, 2.5, -3, *, +]=-6.5
100*50/20=[100, 50, *, 20, /]=250.0
(20+30)*5=[20, 30, +, 5, *]=250.0
2(3+5)/4=[2, 3, 5, +, *, 4, /]=4.0

Comments

[takayuki1107]

ご回答いただきありがとうございます。現時点の僕の知識ではまだコードの大半が理解できてないので、今後学習を進める中でこちらのコードの理解を深めていければと思います。改めてご回答ありがとうございます！

Answer 3

字句解析と構文解析の例を書いて見ました。
ただし、演算子の順位や括弧はない数式の構文解析とします。

import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        System.out.println("数式を入力してください");
        Scanner scanner = new Scanner(System.in);
        String formula = scanner.nextLine();
        Expr e = new Expr(formula);
        int val = e.syn();
        if (e.tok != 0) System.out.println("syntax error");
        else System.out.println(val);
    }
}

class Expr {   // 数式クラス (expression)
    String str;  int len, pos, val;  char tok;

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

    char lex() {  // 字句解析 (lexical analyzer)
        while (pos < len)
            if ((tok = str.charAt(pos++))>='0' && tok<='9') {
                for (val = tok - '0'; pos < len &&
                        (tok = str.charAt(pos))>='0' && tok<='9'; pos++)
                    val = val * 10 + (tok - '0');
                return tok = '0';
            }
            else if (tok != ' ') return tok;
        return tok = 0;  // end of string
    }

    int syn() {  // 構文解析 (syntax analyzer)
        int v = 0;
        for (char op = '+'; lex() != 0; )
            if (tok == '0')
                switch (op) {
                case '+' : v += val; break;
                case '-' : v -= val; break;
                case '*' : v *= val; break;
                case '/' : v /= val; break;
                default: return v;
                }
            else op = tok;
        return v;
    }
}

追記
演算子の優先順位と括弧の処理も追加した構文解析です。

import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        System.out.println("数式を入力してください");
        Scanner scanner = new Scanner(System.in);
        String formula = scanner.nextLine();
        Expr e = new Expr(formula);
        int val = e.syn(0);
        if (e.tok != 0) System.out.println("syntax error");
        else System.out.println(val);
    }
}

class Expr {   // 数式クラス (expression)
    String str;  int len, pos, val;  char tok;

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

    char lex() {  // 字句解析 (lexical analyzer)
        while (pos < len)
            if ((tok = str.charAt(pos++))>='0' && tok<='9') {
                for (val = tok - '0'; pos < len &&
                        (tok = str.charAt(pos))>='0' && tok<='9'; pos++)
                    val = val * 10 + (tok - '0');
                return tok = '0';
            }
            else if (tok != ' ') return tok;
        return tok = 0;  // end of string
    }

    final static char[] op = { '+', '-', '*', '/' };

    int syn(int i) {  // 構文解析 (syntax analyzer)
        int v;
        if (i < 4)
            for (v = syn(i+2); tok == op[i] || tok == op[i+1]; )
                if (tok == '+') v += syn(i+2);
                else if (tok == '-') v -= syn(i+2);
                else if (tok == '*') v *= syn(i+2);
                else v /= syn(i+2);
        else if (lex() == '0') { v = val; lex(); }
        else if (tok == '(') {
            v = syn(0);
            if (tok == ')') lex();
            else tok = 1;
        }
        else v = tok = 1;
        return v;
    }
}

Comments

[takayuki1107]

ご回答いただきありがとうございます。こちら参考にさせていただければと思います。

Answer 4

字句解析 → 構文解析 → スタック

Comments

[takayuki1107]

ご回答ありがとうございます。
キーワードについて調べて理解を深めたいと思います。