スタック Ｃ言語

質問

四則演算のプログラミング(Ｃ++)をスタックを用いて作りたいのですがどうすればいいのか全く分かりません。
スタックの原理は分かるのですが…。

かなり検索してスタックの四則演算を少し見ましたが、まともに載ってるのがあまりなく…。ポーランド記述法つかうのか？とか…ドンドンわからなくなりました。

分かるかた、教えてください。

プログラミング載せてくれたら助かりますが、方針だけでも大丈夫です。

作りたいプログラミングは自分で式を入力して、実行結果にその答えが表示されるというものです。また、入力する式はポーランド記述法のものではなく、普通の式(4*2+1 など)です。

回答No.1

kmee · ベストアンサー

スタックと四則演算とは直接関係のあるのではないですから、単純な検索では難しいでしょうね。

スタックを使った演算というと、よく「逆ポーランド記法」が出てきます。
この記法とスタックとの相性がいいからです。頭から順番に走査して、数値だったらその値をPush,演算子だったら2つPopして演算して結果をPush、を繰り返すだけです。
通常表記の式も、一度逆ポーランド記法に変換すればいいことになります。

演算の解析には、解析木がよくつかわれます。
木ができてしまえば、木の辿り方によって、前置(ポーランド記法)、中置、後置(逆ポーランド記法)での式を求めることができます。

今回は計算だけのようなので、解析木を作る要領で分割しつつ計算するのが効率はよいです。

・式が単項の数値だけ
→スタックに積んでreturn
・それ以外
→式を走査し、解析木のルートになる演算子○を見つける。式=式A ○ 式B
→式Aについて、このアルゴリズムを適用。スタックに結果が積まれる
→式Bについて、このアルゴリズムを適用。スタックに結果が積まれる
→スタックから2つ取り出し、演算○を行い、結果をスタックに積んでreturn

回答No.5

siffon9

No.2、3です。

まずNo.3に漏れがありました申し訳ありません。
No.2の手順をお読みになれば自明ではありますが、最後のelse節を修正します。

else
　記号スタックトップの演算子で数値スタックの上から２個を演算して結果を数値スタックにプッシュ

↓

else
　記号スタックトップの演算子で数値スタックの上から２個を演算して結果を数値スタックにプッシュ
　演算子を記号スタックへプッシュ

さて本題です。
式を計算させるプログラムって結構奥が深いですよ。

> まったくうまくできませんでした。

というのであれば他の方が仰るとおり書籍を参考にすることをお勧めいたします。
目的が四則演算プログラムの作成で、その先（コンパイラ等）へ進まないというのであれば

「やさしいインタプリタの作り方入門」カットシステム、日向 俊二著

をお勧めします、私がいままで読んだ関連本のなかで一番平易な内容でした。

補足

じゃあもういいです（笑）

回答No.4

DoubleHead

4*2+1
などという式(文字列)を解析してスタックを使うアルゴリズムに変換して実行させたい、
ということでしょうか？

で、
その文字列解析の方法がわからない？
スタックを使う方法に変換して実行する方法がわからない？

式の文字列解析については「字句解析」や「構文解析」
「コンパイラの作成」
などの言葉で検索すれば参考になるサイトや書籍がでるでしょう。
もちろん 「C言語」 などの言葉も追加して。

本の１冊や２冊は書けるような代物ですので
ここでプログラムを載せて、っていうのは無理があると思います。

IT関連の書籍が豊富な本屋やアマゾンで
「コンパイラの作り方」
をキーワードに探せばけっこう本がでています。
FORTH言語っていうプログラミング言語があります。
これを調べてみるのも面白いかも。

Javaですが、
http://www.atmarkit.co.jp/fjava/rensai4/compiler05/compiler05_01.html
なんかが参考になると思います。

補足

別にそこまで言ってませんが。

四則演算でスタックを用いたプログラミングが知りたいだけです。

回答No.3

siffon9

No.2の手順をプログラム風にすると以下の様になります。

while(式に残りがある){
　式の左端を持ってくる
　if(持ってきたのが数値)
　　数値スタックにプッシュ
　else // 持ってきたのが演算子
　　if(記号スタックが空)
　　　演算子を記号スタックへプッシュ
　　else if(記号スタックトップより優先順位が高い)
　　　演算子を記号スタックへプッシュ
　　else
　　　記号スタックトップの演算子で数値スタックの上から２個を演算して結果を数値スタックにプッシュ
}

while(記号スタックが空でない){
　記号スタックトップの演算子で数値スタックの上から２個を演算して結果を数値スタックにプッシュ
}

補足

まったくうまくできませんでした。
具体的に教えてもらっていいですか？

回答No.2

siffon9

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.数値スタックに残った値が計算結果です

補足

スタックの原理はわかってますので、式の計算方法は説明なくともわかります。
これをプログラムする方法が分かりません。