計算

[meigin]

こんにちは。

ファイルから読み込んで、命令を実行するというものを作りたいですね。

計算式をどうやって再現すればいいのか解らなくて困っているんです。

１＋１とかなら簡単に解りますが、１＋１＊２＊（１＋４）のような
括弧や掛け算の優先順位とかがあると複雑になります。

・１行単位で扱っている。
・命令　＞　変数名　＞　コメントの順に識別している。
・区切りは　半角空白とコンマだけ
・変数名の次は、数値又は文字列となっている。
・今の所は変数に代入しかできない。
・同じ変数名で型が違っても代入が可能。
・命令の引数は、変数かそのまま利用するのか、エラーかしか判別しない。
・コメントは区切りのない文字列及び数値の事です。
・命令や変数名の前にコメントを書くと変数扱いされてしまう。（意図しない結果になる）
・左上から右下へ順番通りに進む。
・変数名は日本語、英文字どちらでも良い（数値のみでも可能　しかし作動は不明）

現状はこんな感じです。

これ自体のソースは短いんですけど、
多重継承していて大量のファイルになってしまうんですよ。


簡単に考えるなら命令を作くれば良いだけですけど…。
計算式の方が見栄えが良いし分かり易いですよね。

考え方を教えて下さると嬉しいです。

[box]

四則演算の優先順位を満たし、カッコによる優先順位の変更に対応するには、
「数式の木（演算木ともいう）」について考える必要がありそうです。
例題として挙げられた１＋１＊２＊（１＋４）という式から数式の木を構築すると

＋
 ／  ＼
1      ＊
     ／  ＼
   ＊      ＋
 ／  ＼  ／  ＼
1     2  1     4

という結果を得ます。
この木を「帰りがけ順」で走査すると、

1  1  2  *  1  4  +  *  +

となります。この書き方を「逆ポーランド記法」と呼び、
コンピュータで扱いやすくなります（「スタック」というデータ構造とマッチしている）。
また、逆ポーランド記法は数式を日本語読みすることと相性がよいです。
今回の例は
1に「1に2を掛けたものに、1に4を足したものを掛けたもの」を足す
と読めます。

任意の数式から、その数式に対応する「数式の木」を構築できれば、
後はしめたものです。
ただ、その「数式の木」を構築することがなかなか難しそうです。

いくつかのキーワードをちりばめました。
これらをもとに調べてみてはいかがでしょうか。

行ないたいこととずれている、もしくはすでにご存じの内容でしたら、
きれいさっぱり読み捨ててください。

[meigin]

boxさん　ありがとう御座います。

条件分岐が難しくて、思案中です。

数値の次は演算子、
演算子が来たら数値を左へ

演算子に数値が来れば、
数値を右へ

演算子に演算子が来れば？？？
同等なら左へ

上位なら右へ

と思ったのですが。（合っているのか解らない）

ポインタがゴチャゴチャして木自体の構築がいまいち解らないんですね。

データーとポインタを２つ持ったクラスにどんどんnewで繋いで行くんですが……。
こんがらがってしまって、上手く繋げられないのです。

今は試行錯誤中です。

[box]

こちらでも調べてみました。
すると、普通の計算式→数式の木→逆ポーランド記法→計算
という手順の他に、数式の木を構築せずに
普通の計算式→逆ポーランド記法に変換しながら計算
という方法があることがわかりました。

計算用と演算子用の２種類のスタックを用意することと、
演算子に優先順位を設けることがポイントのようです。

混乱させてすみません。

[box]

開きカッコと閉じカッコの優先順位をどのように決めるか
（四則演算子の優先順位との関係をどうするか）がキモのようです。

[meigin]

boxさん

変換しながら計算ですか……。

２番目の演算子が同じ優先順もしくは下位なら前の２つを計算するで合っているのかな？


管理人さん

括弧の演算は一応考えてあります。

まず始めに、括弧を検索して対応しているか調べます。
中身だけ計算して一時的な変数に保持します。

そういう理由で括弧が最優先になります。
中身の優先順位だけ気にすればいいわけですね。



木の構造がいまいち解ってないので、
メモリリークという悲惨な結果しかできませんでした。
情けない。

[Justy]

＞ファイルから読み込んで、命令を実行するというものを作りたい
　このあたりは 2003年１月号のＣマガの記事「コンパイラの作成」を読むとわかりやすいと思います。
　２１ページに渡って解説があり、CDの中にサンプルもありました。

　逆ポーランドだけならそこらに売っているアルゴリズム書にも載ってる気がします。
　定番ですから。

　あとあんましテストしていませんが、（）付きの逆ポーランド化＆計算のサンプルです。
　やっつけなのであまり綺麗じゃないですが、参考にどうぞ。

[ま～く]

書籍ならドラゴンブックと呼ばれているコンパイラの本がありますね。（名前忘れました＾＾；）
これの最初の方に字句解析や構文木の作り方が書いてあって分かりやすいですよ。

以前遊びで作ったコードあるんですけどC++で作っちゃってるからだめですね＾＾；

[meigin]

Justyさん　ありがとう御座います

想像以上に難しいですね。

符号と数字の識別は何処でやっているのか解らないのですが……。
簡単な事しか考えられないので思考が停止して頭から煙が。
色んな方法があるんですね。

うーん。


ま～くさん
コンパイラですか……ハードルが高すぎて想像が付かないです。



取りあえず　木を作って　逆ポーランドにして　計算する
方法を取りました。

間違っていたら教えて下さい。
改善したら早くなるとか、別の方が良いとかありましたら
教えて下さると嬉しいです。

[Justy]

＞符号と数字の識別は何処でやっているのか解らないのですが
　is_opがオペレーションと数値を判別しています。
　isdigit()で数値であることを認識したら node構造体の is_opを偽にしています。
　それ以外で且つ ')'でなければ is_opを真にしています。


＞改善したら早くなるとか、別の方が良いとかありましたら
　本題からは少々外れてしまいますが、幾つか聞かせて下さい。

・　クラス Train/TrainExなどは STLの list/stackに置き換えられると思うのですが、使わない理由は何かあるのでしょうか。

・　これは課題とか学習目的のものでしょうか。それともゲームとかを製作していて、この手のスクリプトを実装しようとしているのでしょうか。

[meigin]

Justyさん

考えることは誰でも一緒ですね。
符号か数値かのフラグだったんですね。
木の右、左の類かと思っていました。


リストを作ったので、苦労した時間を大切にしたいので利用しているだけです。
ＳＴＬを使わない理由は特にないですが、
無料のＶＣ＋＋２００５にはＳＴＬが無かったような記憶があるのでその名残です。


知っていれば応用の幅が広がるという面では学習目的です。
ゲームを作りたいと言うのが本音です。

単にスクリプトの機能をつけるのであれば、そう言ったものを利用すれば良いだけのことです。
即戦力にはなりますが、己の力とはなりません。

知識がないと出来なかったり、想像が付かないんですよ。
これをどうやって再現しているんだろうかとか
気になってたけど、失敗して出来ない。
それでも諦められないと言う執着心があって、
目標となっているわけです。

ゲーム制作はその過程も楽しまなければ良いものは出来ないと思っています。
知識を増やすというのは私にとって喜びなのです。
出来なかったことが出来た時も凄く嬉しいのです。

[Justy]

＠meiginさん
＞木の右、左の類かと思っていました
　私のサンプルでは明示的に木の概念は出てこないので、右も左もなかったりします。


＞リストを作ったので、苦労した時間を大切にしたいので利用しているだけです
　なるほど、わかりました。


＞無料のＶＣ＋＋２００５にはＳＴＬが無かったような記憶があるのでその名残です。
　たしかあったはずでず。
　無いのは Windows専用のライブラリである MFC/ATLとかです。
さすがに C++を謳ったコンパイラで STLがないってのは・・・。


＞知っていれば応用の幅が広がるという面では学習目的です。
　なるほど。だとしたら出来合いのものは使わない方がいいですね。


＞それでも諦められないと言う執着心があって、目標となっているわけです
　これは重要であり、素晴らしいことだと思います。


＞出来なかったことが出来た時も凄く嬉しいのです
　とてもよくわかります。


＞間違っていたら教えて下さい。
　コンパイルが通らない（SetLeftNest()/SetRightNest()内に変数 nがない）というのはありますが、それを除いてもいろいろと挙動が変です。
　ツリーの左と右に分けようとしているのはわかるのですが、SetRightNest()などで mIndex->mpRightとかに既に別の要素が入っているのに newして上書きしたりしているので、前にセットした情報が消えてしまったりしています。

　このソースから手を入れるのはちょっと時間がかかりそうだったので、先のサンプルと meiginさんが添付されたものを融合した物を作ってみました。
　逆ポーランド化されていく仮定が順次表示されるようになっています。

[meigin]

Justyさん

凄い…。

ありがとう御座います。

整理した方が良いかなと思って、コピペして関数にしました。
voidではなくてconst strItem &nとしなければいけませんね。

たまたま、計算通りの結果が出ただけだったんですね。
テキストから読み込んで試したらスタックエラーで止まってしまいました。
考えが甘まかったです。


初めて見る書き方とか勉強になります。
理解するのに時間が掛かりそうです。

[Justy]

＞ありがとう御座います
　まだこれでも完全版ではなかったりします。
　-3とかの数値がこのままでは扱えません。
　更にコメントスキップ、変数対応、代入処理、比較と加えないといけない処理はまだまだありそうです。
　ともあれ、参考になれば幸いです。

[Justy]

＞-3とかの数値がこのままでは扱えません
　なんかプログラマとして負けた気分になってきたので、なんとなく完全対応してみました。

　今回は中身をがらっと変えて、BNF式から書き起こしてみました。

[color=#d0d0ff" face="monospace]factor      ::= integer | '(' expression ')' | '+' factor | '-' factor
term2       ::= factor (('^' factor))*
term1       ::= term2 (('*' term2) | ('/' term2))*
expression  ::= term1 (('+' term1) | ('-' term1))*[/color]

　expressionが解析開始で、" "（空白）はそれに続く、という意味で、
"|"はまたは、*はその前が０回以上繰り返す、という意味です。

　で、この式に当てはめてそのままプログラミングしたのがこの添付のソースです。
　今回はループではなく再帰で、且つ計算可能ならその場で計算していきます。
　ClTest_ki::parse_op()が計算の実行テンプレート関数で、実行内容を関数オブジェクトで指定します。

　この延長線上で考えていけば、比較・評価もやりやすいかもしれません。
　例えば、

[color=#d0d0ff" face="monospace]expression2 ::= expression !(compare_op expression)
compare_op  ::= "==" | "!=" | "<" | ">" | ">=" | "<";[/color]

な感じで。

[meigin]

Justyさん

朝早くからありがとう御座います。

試しに%を追加してみたら、エラー……。
ダブルはダメなんですね。
イントにすると成功しました。

これから比較とかのを頑張って追加しようと思います。


数値でも演算子でもないものは、命令、変数、不明な文字のいずれかになるわけですね。
parse_integerを改造すれば、変数に対応出来そうですね。

再帰は流れが見やすくて良いですね。

[meigin]

Justyさん

色々と勉強になります。

比較、!が追加出来ました。

間違っているのか不安なので添付しておきますね。


最終的にはこちらを使おうと思いますが、
失敗したものをほって前に進めないのでまともに動くように直そうと思っています。

[Justy]

＞試しに%を追加してみたら、エラー……
　std::modulus<>の実装はほんとに "%"演算子を使ってるだけですからね・・・。
　代わりに 自作の関数オブジェクトを作って double型で %演算子と同じ動きをするのを作れば、対応はできるはずです。


＞parse_integerを改造すれば、変数に対応出来そうですね
　はい、そうですね。
　integerの中で対応してもいいですし、別関数にしてもいいですが、そのあたりを修正すれば変数にも対応できます。


＞比較、!が追加出来ました
　お見事です！
　いくつか試しましたが、問題ないようです。


＞失敗したものをほって前に進めないのでまともに動くように直そうと思っています
　そうですね。
　頑張って下さい。


# 自分のコードを改めて見直して。
・parse_factor()の変数 sign_negは使われていないので不要でした。
・power_functor()自体がテンプレートになっていますが、doubleしか扱わないので
double専用の関数にしてしまった方がいいかもしれません。

[meigin]

Justyさん

ありがとう御座います。

ダブル専用でも問題ないですね。
イントにすると大問題でわり算の結果が変わってしまいますね。
%は使い道が無いので非推薦にしておきます。



試行錯誤の末に出来ました。
図に書いたとおりにプログラムを組んだら全く上手く行かず。
その図が間違っていたみたいで、並び替えの末に完成しました。
なんでそれが正しく動くのか解らないんですよ。

まず足し算から初めて、掛け算を加え、（）に対応。


又間違っていたら大変だなと思いつつ添付しておきます。

変なのが入っていますが、test.cppがメインです。
実行するとテキストファイルを読み込んで計算します。
今の状態だと並び替えた数値や演算子が表示されます。

()は木に入れないんですね。
上に登る三つ又になっています。

ファイル読み込みのクラスは継承を外したのでぐちゃぐちゃになってしまいました。
これは関係ないものですので無視して下さい。

[Justy]

＞間違っていたら大変だなと思いつつ添付しておきます

　うーん、サンプルでついていたスクリプトは正しく計算できているようでしたが、

　　1 + (2 - 3) * 4
　とか
　　1 + (2 - 3) * (4 - 5)

　を計算すると間違った結果（それぞれ -9、6）が出ますね。
　()があるとおかしくなるようです。


　それから

　　 1 + 2 - 3* 4
　のように 3と *の間に空白がない場合、4の数字の認識に失敗して演算結果が０になってしまっています。

[Justy]

　今回のプログラムでは影響はないとは思いますが、St.hの TrainExはいくつか問題を抱えているようです。

[color=#d0d0ff" face="monospace]#include <iostream>
#include <crtdbg.h>
#include "St.h"

namespace {
    void disp_trainex_container(St::TrainEx<int> &c){
        using namespace std;
        cout << "te : ";
        for(int n = 0; n < c.Size(); ++n)
            cout << c[n] << " ";
        cout << endl;
    }
}


int main()
{
    _CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF|_CRTDBG_LEAK_CHECK_DF); // メモリリークのチェック
    {
        St::TrainEx<int>    te1, te2;
        for(int n=0; n<8; ++n)
            te1.Push(n);
        disp_trainex_container(te1);        // 0～7が順に表示される
        
        te1.Swep(2, 5);
        disp_trainex_container(te1);        //! 7が２つある！
        
        te1.Pop(1);
        disp_trainex_container(te1);        //! 数値が変わった？
        
        te2 = te1;                      
    }                                       //! 落ちる
    return 0;                               //! リークする
}[/color]

　//! の部分で挙動が想定(?)と違う挙動をするようです。

[meigin]

Justyさん

毎度毎度、申し訳ないです。

TrainExは、たびたび意図しない結果を出すのでその都度修正を行っています。

エラーの原因は、デストラクタで解放しているのでそれで発生していました。
同じアドレスになって、コピーではなく全く同じものを指していました。
te1を変更するとte2の値も変化してしまいます。

=を設定しましたのでエラーは無くなったと思います。

入れ替えは元となったクラスにそう書いてあったので信用してそのままにしていました。
一度もその関数を使わなかったので解りませんでした。
中身だけを入れ替えるように直しました。

読み込み管理は色々と問題があるので作り直す予定です。
計算は繋がっていても出来るようにしました。
その他は必ず半角空白かコンマが必要です。
なので = は半角空白で間を空けて下さい。

三度目の正直になって欲しいです。

色々とご指摘、助かります。

[Justy]

＠meiginさん
＞TrainExは、たびたび意図しない結果を出すのでその都度修正
　先に TrainExなどのコンテナの完成度をある程度上げておいた方がいいかもしれません。
　そうしておけば、使っていて問題がおきたときに TrainEx側には問題ない、と確信できると思います。


＞=を設定しましたので
　代入オペレータを定義したのならついでに
・　同じ変数同士の代入(a=a)への対応
・　*thisの 参照を戻す（a=b=cができるように）
・　コピーコンストラクタを定義

　もしておくといいと思います。
　結構 C++って奥が深く、面倒なんですよね・・・。


＞計算は繋がっていても出来るようにしました
　少し試してみました。かなり良い感じですね。
　ちゃんと変数も認識していますし、あとは負の数への対応くらいでしょうか。
　何にしても後少しです。頑張って下さい。

[meigin]

Justyさん

a = b = c
とか知りませんでした。
勉強になります。

負の数の対応も出来ました。
変数に符号は未対応です。
文字変数もあるので禁止にしていた方が何かと都合が良さそうなので。

これで完成形です。

これは不採用なんですけど。
木を組み立ててから計算しているので無駄が多いと思うので。

色々とありがとう御座います。