Java言語で標準入力で受け取った中置記法の数式を逆ポーランド記法に変換したい。

Question

実現したいこと→Java言語で標準入力で受け取った中置記法の数式を逆ポーランド記法に変換したい。

以前、https://teratail.com/questions/5jykl6q0ug5xmf の質問をさせていただきましたが、それを踏まえて質問させていただいております。まずは、こちらの質問をご覧いただければ幸いです。
こちらの質問を踏まえて逆ポーランド記法に変換したものをスタックを用いる方法で解きたいと考えております。

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

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

ここで標準入力で受け取る数式が中置記法なので、これをまず逆ポーランド記法に直したいです。
↑のURLでの質問でいただいた回答の中には様々ライブラリをインポートしていらっしゃる方もいましたし、ライブラリを使えば簡単に解けるのかもしれませんが、現時点で私はScanner以外のライブラリはほぼ触ったことがなく、Javaの経験も浅いので、コードを提示いただく際にはそういったものを用いないものをいただけると幸いです。

前提

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

私のJavaスキル→勉強し始めて3週間たたない程度。変数宣言、算術演算子、if文での条件分岐、forやwhileなどの繰り返し処理、メソッドの使い方、クラスを分けての開発の仕方などを学びました。
Scanner以外のライブラリに関してはほぼ使ったことがないので、できればソースコードを提示いただく際には使用しないでいただけると非常にありがたいです。
ちなみに、独学ですがPHPは約1年、Pythonは半年ほど勉強しており、基本的な文法は抑えており、PHPはスクラッチで各種バリデーションやログイン機能を備えたアプリを開発したり、Laravelを用いて簡単なアプリを開発したことがあり、PythonはフレームワークにStreamlit、ライブラリにpandasやnumpy、altairなどを使っての簡単なwebアプリ開発の経験があります。
基本情報技術者は保持しており、逆ポーランド記法への変換自体は机上ではできます。(プログラムでの実装方法が分からない状態。)

該当のソースコード

いろいろコードを書いて試してみたのですが、思った通りの挙動に全くならないし、そもそも記述量も少ない段階なので、載せないでおきます。申し訳ございません。

問題を解く手順として自分で考えているもの

標準入力で中置記法(String型)の数式(formulaとする。)を受け取る→
splitで1文字ずつに分割し、配列(formulaArrayとする。)に格納→
formulaArrayを逆ポーランド記法に変換して別の配列に格納(rpnListとする。長さはformulaArray.lengthとする。)→
rpnListからfor文で1要素ずつ取り出して1~9の数字(String型)だったら、スタック(stackという名の配列とする。)に格納。演算子(i番目)が渡ってきたらstackに格納された2つの数字(i-2番目と、i-1番目)をint型に変換後、演算を行い、この結果を変数に格納(int tmpとする)し、再び配列に格納。、、、みたいな感じで解こうと思っています。
まず、最初の中置記法の数式を逆ポーランド記法に変換する段階でどうすればいいのかわからな過ぎて詰まっています。これを標準入力の数式を受け取る際に用いるScanner以外のライブラリは極力使わない形でアルゴリズムを実現したいです。ご協力いただければ幸いです、よろしくお願いいたします。

補足情報（FW/ツールのバージョンなど）

ここにより詳細な情報を記載してください。

Comments

[Zuishin]

ライブラリを使っちゃいけないのは課題だからですよね？
そうでなければ使いましょう。

[takayuki1107]

課題ではありますが、私のJava経験が非常に浅いのが一番の理由です。

[ozwk]

> 最初の中置記法の数式を逆ポーランド記法に変換する段階でどうすればいいのかわからな過ぎて詰まっています。

1. 調べましたか?
2. (調べた場合)それらしき方法を見つけましたか?
3. (見つけた場合)どこがわかりませんでしたか?

[Zuishin]

浅い経験を何とかするためにもっと簡単なことから始めましょう。
ライブラリを使わなければ難易度が下がるということはありません。

[dodox86]

> まず、最初の中置記法の数式を逆ポーランド記法に変換する段階でどうすればいいのかわからな過ぎて詰まっています。

Javaの経験値に限った話ではないように思います。まずは頭の中でできて、その手順を紙にでも書けるか、ではないでしょうか。

[jimbe]

分からない、経験が浅いと言われながら、何故そこを埋めずに先へ行こうとするのでしょうか。
課題として時間が無いのかもしれませんが、それならただの作成依頼にしかなりません。

先の質問への回答にコードを書きましたが、使っているのは今 java をインストールすれば使える機能だけです。
リスト・スタック等は複数のデータを管理する構造としては言語問わず使われるからこそ
標準であるのであって、それを『配列しか使わないで』と言われて では配列でリスト等の実装も書いて付け足せば良いのかといえば、車輪の再発明どころか時間とコード量の無駄でしかありません。

他の言語が出来るなら、まずそちらで動くものを作ってから java に書き換えて見るというのは如何でしょうか。

>逆ポーランド記法への変換自体は机上ではできます

ということなら、それをフローチャートにしてご提示頂くとかのほうが、それに沿ったコードが回答し易いと思います。

[kazuma-s]

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

`2*3+1` と書いてください。「'」ではなくて「`」です。
2(3+5)/4 は「*」を省略していますが、それは意図したものですか？

[xebme]

操車場アルゴリズムは見たことありますか
https://ja.wikipedia.org/wiki/%E6%93%8D%E8%BB%8A%E5%A0%B4%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0
スタックを知らなければ、配列でスタックを自作しましょう。

カーニハン＆リッチーのC言語の教科書は、ワンステップずつ計算器を作る内容だったと思います。これなんか、Javaに置き換えてみるのも良いでしょう。

カンニングしたければ、https://www.freecodecamp.org/learn/coding-interview-prep/rosetta-code/
でも実力がなければいつか去らなければなりません。
ちょと言いすぎました。実力というのは、自力で、数行のコードからなんとか動作するコードを作る、粘り強さ、しつこさのことです。時間をかけてください。

Answer 1

リストを配列で定義し、スタックはそのリストを利用するように定義、正規表現をコード化、内部クラスの殆どを展開しました。
簡単になったとは思えませんが…。

係数優先モード指定追加。 6/2(1+2) の結果を選べます。(true なら 1、 false なら 9)

class List {
  private String[] values = new String[0];
  private int size = 0;
  List() {}
  List(List org) {
    size = org.size;
    values = new String[org.values.length];
    for(int i=0; i<size; i++) values[i] = org.values[i];
  }
  /** 最後に追加
   * @param v 追加するデータ */
  void add(String v) {
    if(size == values.length) {
      String[] newValues = new String[values.length + 10];
      for(int i=0; i<size; i++) newValues[i] = values[i];
      values = newValues;
    }
    values[size++] = v;
  }
  /** i 番目を削除
   * @param i インデックス(0 ～ size()-1)
   * @return 削除したデータ */
  String remove(int i) {
    String v = values[i];
    for(size--; i<size; i++) values[i] = values[i+1];
    return v;
  }
  /** i 番目を取得
   * @param i インデックス(0 ～ size()-1)
   * @return データ */
  String get(int i) { return values[i]; }
  /** i 番目を変更
   * @param i インデックス(0 ～ size()-1)
   * @param v データ */
  void set(int i, String v) { values[i] = v; }
  /** 件数
   * @return 件数 */
  int size() { return size; }
  @Override
  public String toString() {
    String s = "[";
    for(int i=0; i<size; i++) s += (i>0?", ":"") + values[i];
    s += "]";
    return s;
  }
}

class Stack {
  private List list = new List();
  /** トップに追加
   * @param v 追加するデータ */
  void push(String v) { list.add(v); }
  /** トップから取り出し
   * @return データ */
  String pop() { return list.remove(list.size()-1); }
  /** トップを確認
   * @return データ */
  String peek() { return list.get(list.size()-1); }
  /** 空判定
   * @return 空なら true */
  boolean isEmpty() { return list.size() == 0; }
}

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", "1+(2(3+((5/2)-2)))", "6/2(1+2)" };
    for(String formula : testdata) {
      RPN rpn = new RPN(formula, true);
      System.out.println(rpn + "=" + rpn.calc());
    }
  }

  private static class RPN {
    private static class Translator {
      private final String formula;
      private int index;
      private Stack stack = new Stack();
      private List list = new List();

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

      List translate(boolean coefficientPriorityMode) {
        int mode = 0;
        while(!isEnd()) {
          if(mode == 0) {
            if(getChar() == '(') {
              putOp(nextOperator());
            } else {
              putValue(nextNumber());
              mode = 1;
            }
          } else {
            String op = nextOperator();
            if(op.equals(")")) {
              putOp(op);
            } else {
              if(op.equals("(")) putOp(coefficientPriorityMode ? "**" : "*");
              putOp(op);
              mode = 0;
            }
          }
        }
        return complete();
      }

      private boolean isEnd() { return index >= formula.length(); }
      private char getChar() { return formula.charAt(index); }
      private String nextOperator() {
        String op = "" + formula.charAt(index++);
        if("+-*/()".indexOf(op.charAt(0)) < 0) throw new IllegalArgumentException("Operator Error: index=" + index);
        return op;
      }
      private String nextNumber() {
        int j, i = index + (formula.charAt(index)=='-'?1:0);
        for(j=0; i<formula.length() && ('0'<=formula.charAt(i) && formula.charAt(i)<='9'); i++, j++);
        if(j > 0 && i < formula.length() && formula.charAt(i) == '.') {
          for(i++, j=0; i<formula.length() && ('0'<=formula.charAt(i) && formula.charAt(i)<='9'); i++, j++);
        }
        if(j == 0) throw new IllegalArgumentException("Number Error: index=" + index);
        String v = formula.substring(index, i);
        index = i;
        return v;
      }

      private void putOp(String op) {
        if(op.equals(")")) {
          while(!stack.isEmpty() && !(op=stack.pop()).equals("(")) list.add(op.toString());
          if(!op.equals("(")) throw new IllegalStateException("Formula Error: Unmatched parentheses.");
          return;
        }
        if(!op.equals("(")) {
          while(!stack.isEmpty() && getPri(stack.peek()) >= getPri(op)) list.add(stack.pop());
        }
        stack.push(op);
      }
      private int getPri(String op) {
        if(op.equals("**")) return 3;
        if(op.equals("*") || op.equals("/")) return 2;
        if(op.equals("+") || op.equals("-")) return 1;
        return 0;
      }
      private void putValue(String v) {
        list.add(v);
      }
      private List complete() {
        while(!stack.isEmpty()) list.add(stack.pop());
        for(int i=0; i<list.size(); i++) if(list.get(i).equals("**")) list.set(i, "*");
        return new List(list);
      }
    }

    private final String formula;
    private List list;

    RPN(String formula, boolean coefficientPriorityMode) {
      this.formula = formula;
      list = new Translator(formula).translate(coefficientPriorityMode);
    }

    String calc() {
      Stack stack = new Stack();
      for(int i=0; i<list.size(); i++) {
        String s = list.get(i);
        if(s.equals("+")) {
          double b = Double.parseDouble(stack.pop());
          double a = Double.parseDouble(stack.pop());
          stack.push("" + (a + b));
        } else if(s.equals("-")) {
          double b = Double.parseDouble(stack.pop());
          double a = Double.parseDouble(stack.pop());
          stack.push("" + (a - b));
        } else if(s.equals("*")) {
          double b = Double.parseDouble(stack.pop());
          double a = Double.parseDouble(stack.pop());
          stack.push("" + (a * b));
        } else if(s.equals("/")) {
          double b = Double.parseDouble(stack.pop());
          double a = Double.parseDouble(stack.pop());
          stack.push("" + (a / b));
        } else {
          stack.push(s);
        }
      }
      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
1+(2(3+((5/2)-2)))=[1, 2, 3, 5, 2, /, 2, -, +, *, +]=8.0
6/2(1+2)=[6, 2, 1, 2, +, *, /]=1.0

Answer 2

このコードは参考になりますか？

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);
        e.syn(0);
        if (e.tok != 0) System.out.println("syntax error");
        else System.out.println(e.rpn);
    }
}

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

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

    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 = { '+', '-', '*', '/' };

    void syn(int i) {  // 構文解析 (syntax analyzer)
        if (i < 4)
            for (syn(i+2); tok == op[i] || tok == op[i+1]; ) {
                char t = tok;
                syn(i+2);
                rpn += t + " ";
            }
        else if (lex() == '0') {
            rpn += val + " ";
            lex();
        }
        else if (tok == '(') {
            syn(0);
            if (tok == ')') lex();
            else tok = 1;
        }
        else tok = 1;
    }
}

Scanner 以外の特別なクラスは使っていません。
理解できないのはどこですか？