Javaで逆ポーランド記法変換・計算プログラムを作ってみた(変換編)
※追記
ﾋﾟｨｨｨｨｨﾎﾟｫｫｫｫｫﾋﾟｨｨｨｨｨﾎﾟｫｫｫｫ
バグ絶対許さない警察です、あなたにバグ警告書が届いています。数週間以内にデバッグを行ってください。
ということでバグがあったので、デバッグついでにリファクタリングとかもしたのを最後の方に追加します。
コメントくれた方、ありがとうございます…！
どうも、じゃがいもではないポテトのポテト君です(?)
ということで前回準備編をしたので
変換をやっていきます。
普通に変換を行う場合、文字に置き換えれば分かりやすく変換できました。
それをそのままプログラムにしてもいいのですが、今回は計算のときと同じように、スタックを使用して変換していきます。
まずは、式をString型で渡したらRPNに変換してString型で返すrp関数を定義したものとして、それ以外の処理を書きます。
import java.io.*;
import java.util.regex.*;
import java.util.*;
public class RPN{
public static void main(String[] args) throws IOException{
System.out.println("you can use \"1~9.()+-*/\"\nwrite formula");
BufferedReader read=new BufferedReader(new InputStreamReader(System.in));
String form=read.readLine();
System.out.println("="+rp(form));
System.out.println("="+String.valueOf(rpcal(rp(form))));
}
キーボード入力で式を受け取って結果を表示するだけのプログラムです。
importしたものは後に使用します。
rpcal関数はRPNを計算してdouble値を返す関数とします。
この10.~11.の間に関数の宣言を追加していきます。
さて関数の処理内容を書いていく前に、スタックで式をRPNにする手順を考えていきます。
まず、( )のない式を考えてみます。
a+b*c
この式を先頭から読んでいくと
1.aを結果に追加
2.+は*/が来るかもしれないので保留(スタックに追加)
3.bを結果に追加
4.*は要素の後ろにくるので保留(スタックに追加)
5.cは結果に追加
6.演算子をスタックから取り出して結果に追加
そうすると
abc*+
というRPNが得られ、a+b*cが変換されたことになる。
a*b+c
だったらどうでしょうか
1.aを結果に追加
2.*は要素の後ろにくるので保留(スタックに追加)
3.bを結果に追加
4.+は要素の後ろにくるので保留(スタックに追加)、*は優先するのでスタックから取り出して結果に追加
5.cは結果に追加
6.演算子をスタックから取り出して結果に追加
結果は
ab*c+
となります(abc+*とはしないように)
加減法と乗除法はそれぞれ優先度が等しいので同じように扱えます。
ただのこのままだと、準備編でも言ったように
a-b+c
が
abc+-
になり
a-(b+c)
となってしまうため、これを直さなければいけません。
なので、+か-を読み取ったとき、スタックに+か-が入っていればそれを結果に追加するというようにすれば
a-b+c
は
ab-c+
となり
a-b+c
に戻すことができます。
乗除法についても同じようにします。
※追記
これで、スタックの中身は[+または-]、[*または/]、[*または/ , +または-]以外のパターンを取らなくなります。
[+,+]のようにならないのは上記のようにするからです。
[-,*]のようにならないのは、*の次に-が来た時にはスタックから*を取り出さなければならないからです。(*の方が優先するため)
ここまではいいのですが、[*,-]のときに-が来たらどうなるでしょうか。
この場合-,*,-という順番で演算子が置いてあることになります。*は優先するのでもちろんスタックから取り出しますが、-も上記のabc+-を避ける理由と同じでプッシュします。
(a-b*c-d -> abc*-d- になる、ここで-をプッシュしないと abc*d--となり、中置記法に直すとa-(b*c-d)となってしまいます。)
ここがデバッグ前でバグるところです。
これが分かれば、( )付きの式についても変換できます。
( )内を計算した結果は1つの要素と考えられるので
(を読み取った時に、)までの数式を計算して、それを結果に追加すればいいわけです。
これで、数式をRPNに変換する方法が分かりました。
ということでこれをプログラムにしていきます。
関数の部分だけ書きます。
static String rp(String form){
form="("+form+")";
Pattern mi=Pattern.compile("\\((-\\d+\\.?\\d*)\\)");
Matcher mat=mi.matcher(form);
while(mat.find()){
form=form.substring(0,mat.start())+"["+mat.group(1)+"]"+form.substring(mat.end());
mat=mi.matcher(form);
}
Pattern tocha=Pattern.compile("[^\\[0-9](\\d+\\.?\\d*)[^\\]0-9]");
mat=tocha.matcher(form);
while(mat.find()){
form=form.substring(0,mat.start(1))+"["+mat.group(1)+"]"+form.substring(mat.end(1));
mat=tocha.matcher(form);
}
form=form.substring(1,form.length()-1);
boolean stop=false;
int kaknow=0;
char[] formc=form.toCharArray();
StringBuilder ret=new StringBuilder(formc.length),kakst=new StringBuilder(formc.length);
Deque<Character> sta=new ArrayDeque<>();
for(char c:formc){
if(!stop){
switch(c){
case '+':
case '-':
if(ret.toString().charAt(ret.length()-1)=='['){
ret.append(c);
break;
}
if(!sta.isEmpty()){if(sta.getFirst()=='+'||sta.getFirst()=='-')ret.append(sta.removeFirst());}
while(!sta.isEmpty()){
if(sta.getFirst()=='*'||sta.getFirst()=='/')ret.append(sta.removeFirst());
else break;
}
sta.addFirst(c);
break;
case '*':
case '/':
if(!sta.isEmpty()){if(sta.getFirst()=='*'||sta.getFirst()=='/')ret.append(sta.removeFirst());}
sta.addFirst(c);
break;
case '(':
stop=true;
kaknow=1;
break;
default:
ret.append(c);
break;
}
}else{
switch(c){
case '(':
kaknow++;
kakst.append(c);
break;
case ')':
kaknow--;
if(kaknow==0){
String kakret=rp(kakst.toString());
ret.append(kakret);
stop=false;
}else kakst.append(c);
break;
default:
kakst.append(c);
break;
}
}
}
while(!sta.isEmpty())ret.append(sta.removeFirst());
form=ret.toString();
return form;
}
いやー長いですね。
2~15は式に含まれる数値を全て[ ]で囲む処理です。
(
( )内の式を計算する時にこの関数は再帰処理を行うので、2回目以降は結果は変わらないため無駄な処理になるので飛ばそうと思いましたが、それを引数でどうにかしようと思ったときにJavaにはデフォルト引数がなくてですね、わざわざオーバーロードするのもプログラムが長くなって嫌なので、他の方法もあるかもだけどもうめんどくさいしこのままにしました。
)正規表現の簡略化の諸々(追記:正数を囲むとき、前後に何かしらの記号がある前提としているからです)で、2.で式全体を( )で囲い15.で外しています。
負数と正数は別々に囲っていて、3~8は負数を[ ]囲む部分です。
3.で正規表現を"\\( ( - \\d+ \\.? \\d* ) \\)"としていますが、( )内に負数値が入ってる場合のみを考えてます。省略可にするとめんどいので負数は必ず( )で囲って扱うものとします。
\\.? \\d*としているのは、小数に対応させるためです。
グループ化の( )とエスケープした( )が紛らわしいのはどうにもなりません…ｗ
5~8のwhile文で、正規表現にマッチする部分がなくなるまでマッチしたものを[ ]で囲っています。
9~14は正数を[ ]で囲む処理です。
今考えると全ての正数を( )で囲む処理をしてから、3~8を3.の正規表現を"\\( ( -? \\d+ \\.? \\d* ) \\)"にして実行した方がプログラムが短くなったかなーと思いました(とりあえずプログラムを短くしたい人)。
16~71がこの関数の本題です。
16.のstopは、(を読み取ったときにtrueを入れて変換処理をとめ、かっこが閉じるまで文字を保存する処理に切り替えるための変数です。
( )内に( )が入れ子になっていることもあるので、(を読み取ったときに17.のkaknowをインクリメントし、)を読み取ったときにデクリメントします。
そうすれば、kaknowが0になったときに最初に読み取った(がそこで閉じると分かります。
18.でRPNを表す文字列を文字の配列にして21~69のfor文で1文字ずつ読み取っていきます。
19.ではStringBuilderを使っていますが、馴染みが薄いのでStringでもよかったかもです。文字を追加していって文字列が作れるやーつです(説明がテキトー)。retは結果を、kakstは( )内の文字を追加します。
20が今回使うスタックです。なんでDequeなんでしょうか、queueのdequeueと紛らわしいですね()
21~69のfor文で文字を1文字ずつ読み取っています。22~49のif文が( )内ではないときの処理、50~68のelse部は( ) 内の処理です。
読み取った文字はswitch文で判定していきます。
23~49では、'+'を読み取った時、'*'を読み取った時はわざとbreak文を書かず、それぞれcase '-'、'/'のところで '-'、'/'と同様に処理を行います。
'-'のところで注意すべき点は、減算だけでなく[ ]の中が負数の場合にもでてくるということです。
そのため'-'を読み取った時に26~29ではretに1つ前に追加した文字が'['の時はretに追加するようにしています。
51~67では、文字をkakstに追加し、(であればkaknowをインクリメント、)であればデクリメントし、0になったらkakstを文字列にしてrp関数に渡し(再帰処理)、返り値を結果に追加します。
70ではスタックから演算子をとりだして結果に追加しています。これをString型にすればRPNの完成!
ということで変換ができました。
(この時点で実行する場合最初の方で書いたrpcal関数を使った行は消してください。)
試しに
10+5*(2-(-8))
と入力すれば
=[10][5][2][-8]-*+
と返されるはずです。
次回はこのRPNを計算していきます。また次回！
※追記
冒頭で言った改善後のプログラムのrp関数(名前をmakeRPN関数に変えています)部分を貼ります。
/**
* 中置記法の数式をRPNに変換します。
* 数字は[]で囲んで返されます。
*
* @param form 数式
* @return String RPN
*/
static String makeRPN(String form) {
form = "(" + form + ")"; // 一時的に()を付ける
Pattern minus_pattern = Pattern.compile("\\((-\\d+\\.?\\d*)\\)"); // 負数のパターン
Matcher matcher = minus_pattern.matcher(form); // マッチャー
while (matcher.find()) { // 負数を全て[]で囲む
form = form.substring(0, matcher.start()) + "[" + matcher.group(1) + "]" + form.substring(matcher.end());
matcher = minus_pattern.matcher(form);
}
Pattern plus_pattern = Pattern.compile("[^\\[0-9](\\d+\\.?\\d*)[^\\]0-9]"); // 正数のパターン
matcher = plus_pattern.matcher(form);
while (matcher.find()) { // 正数を全て[]で囲む
form = form.substring(0, matcher.start(1)) + "[" + matcher.group(1) + "]" + form.substring(matcher.end(1));
matcher = plus_pattern.matcher(form);
}
form = form.substring(1, form.length() - 1); // 一時的に付けた()を外す
boolean stop = false; // ()が出たときに処理を切り替えるため
int bracket_count = 0; // 現在位置の文字で()の重なっている個数
String ret = ""; // 返り値
String inner_string = ""; // ()内の文字列
Deque<Character> stack = new ArrayDeque<>(); // スタック
for (char c : form.toCharArray()) { // 文字を先頭から1つずつ取り出す
if (!stop) { // ()内でなければ
switch (c) {
case '+':
case '-': // +と-の優先度は同じなので同じ処理をする
if (ret.charAt(ret.length() - 1) == '[') { // 前の文字が[なら
ret += c; // 負数を示す-なのでそのまま追加
break; // これ以降は減算の処理なのでbreak
}
while (!stack.isEmpty()) {
ret += stack.pop(); // スタックの中身を全て追加
}
stack.push(c); // スタックに演算子をプッシュ
break;
case '*':
case '/': // *と/の優先度は同じ
if (!stack.isEmpty()) { // 1度しか行われない
if (stack.peek() == '*' || stack.peek() == '/')
ret += stack.pop();
// +や-より優先度が高いので、*と/のみ追加
}
stack.push(c); // 演算子をプッシュ
break;
case '(':
stop = true; // ()が来たら処理を変える
bracket_count = 1; // ()のカウントは1に
break;
default:
ret += c;
break;
}
} else { // ()内の処理
switch (c) {
case '(':
bracket_count++; // (ならカウントを増やす
inner_string += c;
break;
case ')':
if (--bracket_count == 0) { // )ならカウントを減らし、それが0なら
ret += makeRPN(inner_string.toString()); // ()内で再帰処理
stop = false; // ()内の処理を抜ける
} else
inner_string += c;
break;
default:
inner_string += c;
break;
}
}
}
while (!stack.isEmpty())
ret += stack.pop(); // スタックに残ったものを追加する
return ret;
}名前とか処理とか色々変えたりしてますが、本質的には大して変化ないのでコメントを読んでください()
デバッグした部分は、switch文の+-を処理する部分で、スタックの中身を無条件で全て追加するようにしたということです。
リファクタリングとしてスタックのaddFirst/removeFirst関数をpush/pop関数に、getFirst関数をpeek関数にしました。