四則演算のプログラミング(C++)をスタックを用いて作りたいのですがどうすればいいのか全く分かりません。
スタックの原理は分かるのですが…。
かなり検索してスタックの四則演算を少し見ましたが、まともに載ってるのがあまりなく…。ポーランド記述法つかうのか?とか…ドンドンわからなくなりました。
分かるかた、教えてください。
プログラミング載せてくれたら助かりますが、方針だけでも大丈夫です。
作りたいプログラミングは自分で式を入力して、実行結果にその答えが表示されるというものです。また、入力する式はポーランド記述法のものではなく、普通の式(4*2+1 など)です。
No.1ベストアンサー
- 回答日時:
スタックと四則演算とは直接関係のあるのではないですから、単純な検索では難しいでしょうね。
スタックを使った演算というと、よく「逆ポーランド記法」が出てきます。
この記法とスタックとの相性がいいからです。頭から順番に走査して、数値だったらその値をPush,演算子だったら2つPopして演算して結果をPush、を繰り返すだけです。
通常表記の式も、一度逆ポーランド記法に変換すればいいことになります。
演算の解析には、解析木がよくつかわれます。
木ができてしまえば、木の辿り方によって、前置(ポーランド記法)、中置、後置(逆ポーランド記法)での式を求めることができます。
今回は計算だけのようなので、解析木を作る要領で分割しつつ計算するのが効率はよいです。
・式が単項の数値だけ
→スタックに積んでreturn
・それ以外
→式を走査し、解析木のルートになる演算子○を見つける。式=式A ○ 式B
→式Aについて、このアルゴリズムを適用。スタックに結果が積まれる
→式Bについて、このアルゴリズムを適用。スタックに結果が積まれる
→スタックから2つ取り出し、演算○を行い、結果をスタックに積んでreturn
No.5
- 回答日時:
No.2、3です。
まずNo.3に漏れがありました申し訳ありません。
No.2の手順をお読みになれば自明ではありますが、最後のelse節を修正します。
else
記号スタックトップの演算子で数値スタックの上から2個を演算して結果を数値スタックにプッシュ
↓
else
記号スタックトップの演算子で数値スタックの上から2個を演算して結果を数値スタックにプッシュ
演算子を記号スタックへプッシュ
さて本題です。
式を計算させるプログラムって結構奥が深いですよ。
> まったくうまくできませんでした。
というのであれば他の方が仰るとおり書籍を参考にすることをお勧めいたします。
目的が四則演算プログラムの作成で、その先(コンパイラ等)へ進まないというのであれば
「やさしいインタプリタの作り方入門」カットシステム、日向 俊二著
をお勧めします、私がいままで読んだ関連本のなかで一番平易な内容でした。
No.4
- 回答日時:
4*2+1
などという式(文字列)を解析してスタックを使うアルゴリズムに変換して実行させたい、
ということでしょうか?
で、
その文字列解析の方法がわからない?
スタックを使う方法に変換して実行する方法がわからない?
式の文字列解析については「字句解析」や「構文解析」
「コンパイラの作成」
などの言葉で検索すれば参考になるサイトや書籍がでるでしょう。
もちろん 「C言語」 などの言葉も追加して。
本の1冊や2冊は書けるような代物ですので
ここでプログラムを載せて、っていうのは無理があると思います。
IT関連の書籍が豊富な本屋やアマゾンで
「コンパイラの作り方」
をキーワードに探せばけっこう本がでています。
FORTH言語っていうプログラミング言語があります。
これを調べてみるのも面白いかも。
Javaですが、
http://www.atmarkit.co.jp/fjava/rensai4/compiler …
なんかが参考になると思います。
No.3
- 回答日時:
No.2の手順をプログラム風にすると以下の様になります。
while(式に残りがある){
式の左端を持ってくる
if(持ってきたのが数値)
数値スタックにプッシュ
else // 持ってきたのが演算子
if(記号スタックが空)
演算子を記号スタックへプッシュ
else if(記号スタックトップより優先順位が高い)
演算子を記号スタックへプッシュ
else
記号スタックトップの演算子で数値スタックの上から2個を演算して結果を数値スタックにプッシュ
}
while(記号スタックが空でない){
記号スタックトップの演算子で数値スタックの上から2個を演算して結果を数値スタックにプッシュ
}
No.2
- 回答日時:
No.1様の方法より、単純なやり方を説明してみます。
式 1+2*3+4 の場合、式を左から順にみていきます。
1. '1'を数値スタックに積む
数値スタック:1 (データはスタックへ左から右へ積まれるとします)
記号スタック:なし
式の残り :+2*3+4
2. '+'を記号スタックに積む
数値スタック:1
記号スタック:+
式の残り :2*3+4
3. '2'を数値スタックに積む
数値スタック:1,2
記号スタック:+
式の残り :*3+4
4. '*'は記号スタックトップにある'+'より優先順位が高いのでスタックに積む
数値スタック:1,2
記号スタック:+,*
式の残り :3+4
5. '3'を数値スタックに積む
数値スタック:1,2,3
記号スタック:+,*
式の残り :+4
6. '+'は記号スタックトップにある'*'より優先順位が低いので、記号スタックのトップの'*'で数値スタックのトップから二つの数値を計算し、その結果を数値スタックに積む
数値スタック:1,6
記号スタック:+
式の残り :+4
7. '+'を記号スタックに積む
数値スタック:1,6
記号スタック:+,+
式の残り :4
8. '4'を数値スタックに積む
数値スタック:1,6,4
記号スタック:+,+
式の残り :なし
9. 式が無くなったので、記号スタックのトップの記号で数値スタックのトップから二つの数値を計算し、その結果を数値スタックに積む
数値スタック:1,10
記号スタック:+
式の残り :なし
10.同上
数値スタック:11
記号スタック:なし
式の残り :なし
11.数値スタックに残った値が計算結果です
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- その他(コンピューター・テクノロジー) 量子コンピュータの動作原理がわかりません。同じビットが、1でも0でも有って良いだろうか? 3 2023/02/04 03:20
- その他(プログラミング・Web制作) プログラミングって本来数学的な計算をする為のものではないのですか? 学校で配られたFortran90 11 2022/08/25 22:14
- その他(自然科学) 科学技術計算の仕事について 2 2023/02/04 18:09
- Excel(エクセル) 下記エクセルの式がなぜこうなるのか理由が知りたいです。 6 2022/08/20 00:43
- C言語・C++・C# 3×3のラテン方陣をつくるプログラムを作成したのですが、(↓) #include <stdio.h> 5 2023/07/10 01:53
- C言語・C++・C# 至急教えてください。プログラミングの問題です。 最初に正の整数nの入力を受け付け、次に分数の分子と分 1 2022/07/19 17:03
- 法学 コンピューター プログラミングの言語で記述されたプログラミングのコード一式は、作った人に 著作権があ 4 2023/08/04 17:31
- C言語・C++・C# 至急お願いします。プログラミングの問題です。 最初に正の整数nの入力を受け付け、次に分数の分子と分母 3 2022/07/19 17:09
- C言語・C++・C# プログラミング初心者です。 演算子を習い、自力で計算機を作ろうと思い、写真のようなプログラムを書きま 2 2022/08/14 21:27
- その他(プログラミング・Web制作) Pythonを用いたフラッシュ暗算ソフトの開発に必要なもの 2 2023/01/29 02:22
関連するカテゴリからQ&Aを探す
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
ゆゆにゃ。
-
エラー?メッセージ
-
最大スタックサイズを大きくす...
-
H8マイコン スタック領域に...
-
pthreadのスタックサイズ設定取...
-
ポーランド記法、逆ポーランド...
-
スタックを用いて整数配列を入...
-
マス目上の移動のアルゴリズム
-
スタック領域変更
-
iPhoneとituneの同期を付属のUS...
-
スタックとキューの使い所
-
gccでスタックサイズを変更する...
-
プログラムの規模を表す単位「k...
-
パソコンでインターネット接続...
-
hdmiはパラレル?シリアル?
-
ubuntuで デイスク/deb/loopと...
-
ライン数とステップ数の違いに...
-
命令口調について
-
ブラインドタッチ
-
ワープロ検定の勉強法について。
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
VB.netでDLLを読み込んで実行す...
-
最大スタックサイズを大きくす...
-
printf / sprintf のスタック消...
-
エラー?メッセージ
-
スタックフレームの消滅
-
_CRTIMPの意味は?
-
関数のプロローグとエピローグ...
-
逆ポーランド記法
-
マス目上の移動のアルゴリズム
-
C言語・スタックを使用した逆...
-
CASLとCASL2の違いについて
-
スタック領域変更
-
Cプログラミングの関数電卓のア...
-
スタック C言語
-
再帰処理を非再帰処理に書き換...
-
gccでスタックサイズを変更する...
-
スタックを用いて整数配列を入...
-
スタックの仕組み
-
スタックの伸張方向
-
H8マイコン スタック領域に...
おすすめ情報