掲示板利用宣言

 次のフォームをすべてチェックしてからご利用ください。

 私は

 題名と投稿者名は具体的に書きます。
 課題の丸投げはしません。
 ソースの添付は「HTML変換ツール」で字下げします。
 返信の引用は最小限にします。
 環境(OSとコンパイラ)や症状は具体的に詳しく書きます。
 返信の付いた投稿は削除しません。
 マルチポスト(多重投稿)はしません。

掲示板2

管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    ログ    タグ一覧

No.24248

文字列で与えられた式の評価
投稿者---だん(2005/11/19 20:54:09)


だんと申します。

皆様のご意見を聞かせていただきたく書き込みしています。

例えば文字列で
(3 + 2) + 10 * ( 5 / ( 29 + 1 ) )
と与えられた場合
この演算結果を求めたいのですが、

アルゴリズムが思いつかない為、
ご助力ください。
また、いろいろ調べていて
逆ポーランド法という言葉を
目にしました。関係ありますでしょうか?

アルゴリズムの質問なので、
関係ないとは思いますが
開発環境はWinXPSP2 VC++6.0 です。



この投稿にコメントする

削除パスワード

発言に関する情報 題名 投稿番号 投稿者名 投稿日時
<子記事> Re:文字列で与えられた式の評価 24249 DD. 2005/11/19 21:05:42
<子記事> Re:文字列で与えられた式の評価 24250 Blue 2005/11/19 21:09:30
<子記事> Re:文字列で与えられた式の評価 24254 pseudo 2005/11/19 23:13:25
<子記事> Re:文字列で与えられた式の評価 24317 だん 2005/11/22 18:23:16


No.24249

Re:文字列で与えられた式の評価
投稿者---DD.(2005/11/19 21:05:42)


>例えば文字列で
>(3 + 2) + 10 * ( 5 / ( 29 + 1 ) )
>と与えられた場合
>この演算結果を求めたいのですが、
aton()で文字から数値に変換できます。
記号はif文なりで判定してやればよいかと。


この投稿にコメントする

削除パスワード

No.24251

Re:文字列で与えられた式の評価
投稿者---だん(2005/11/19 21:11:08)


与えられる文字列は動的です。
簡単にif文などで実現できますでしょうか?
while文で文字列を先頭から
解釈していくと思うのですが
後に()や*/などが出てきた場合、
演算がややこしくなると思うのですが...


この投稿にコメントする

削除パスワード

No.24252

Re:文字列で与えられた式の評価
投稿者---shu(2005/11/19 22:07:37)


(3 + 2) + 10 * ( 5 / ( 29 + 1 ) )
5 + 10 * ( 5 / ( 29 + 1 ) )
5 + 10 * ( 5 / 30 )
5 + 10 * 0
5 + 0
5


まずは、優先的に計算すべきところを1箇所だけ計算。
計算結果を反映して、元の式の文字列の書き換え。

あとは、答えが出るまでそれの繰り返し。


この投稿にコメントする

削除パスワード

No.24263

Re:文字列で与えられた式の評価
投稿者---DD.(2005/11/20 10:06:50)


>簡単にif文などで実現できますでしょうか?
() や * or / 等の優先順位の高いものを先に
計算→展開してやればできるかと。

>演算がややこしくなると思うのですが...
もっと簡単な方法はありそうですが。。。
まぁその人次第ということで^^;


この投稿にコメントする

削除パスワード

No.24264

Re:文字列で与えられた式の評価
投稿者---DD.(2005/11/20 10:08:00)


ってshuさんから先に同じ回答でてましたorz


この投稿にコメントする

削除パスワード

No.24250

Re:文字列で与えられた式の評価
投稿者---Blue(2005/11/19 21:09:30)


・字句解析
・構文解析
というのを調べられると良いと思います。

まだ、過去ログになっていないので ログ にしかなっていませんが、
似たような質問があったので参考にしてください。
http://bbslog.realint.com/?serverid=2&bbsid=pointc&page=7
No.23576
関数、変数を入力して結果を出力する方法
# ログなので時間が経つと参照できなくなりますので。


この投稿にコメントする

削除パスワード

No.24266

Re:文字列で与えられた式の評価
投稿者---かずま(2005/11/20 16:03:31)


> # ログなので時間が経つと参照できなくなりますので。

それと、< が &lt; になっていたり、字下げがなくて、プログラムを読み
取ることが難しいでしょう。いつものプログラムを挙げて起きます。
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

int c;  char *p, o[] = "+-*/";

int get(void) { do c = *p++ & 0xff; while (isspace(c)); return c; }

double expr(const char *s)
{
    double v;
    if (*s)
        for (v = expr(s + 2); c == s[0] || c == s[1];)
            switch (c) {
            case '+': v += expr(s + 2); break;
            case '-': v -= expr(s + 2); break;
            case '*': v *= expr(s + 2); break;
            case '/': v /= expr(s + 2); break;
            }
    else if (get() == '.' || isdigit(c)) v = strtod(p - 1, &p), get();
    else if (c == '(') v = expr(o), c == ')' ? get() : (c = 1);
    else v = c = 1;                /* error */
    return v;
}

int main(void)
{
    char buf[1024];  double v;

    while (fgets(p = buf, sizeof buf, stdin))
        v = expr(o), printf(c ? "  error\n" : "  %.15g\n", v);
    return 0;
}



この投稿にコメントする

削除パスワード

No.24278

Re:文字列で与えられた式の評価
投稿者---管理人(2005/11/21 00:09:09)


>まだ、過去ログになっていないので ログ にしかなっていませんが、
>似たような質問があったので参考にしてください。

ご迷惑お掛けします。
UPしましたので、こちらの方をご覧ください。
http://f4.aaa.livedoor.jp/~pointc/No.23576.html


この投稿にコメントする

削除パスワード

No.24279

Re:文字列で与えられた式の評価
投稿者---Blue(2005/11/21 01:06:35)


>ご迷惑お掛けします。
ありがとうございます。
こちらこそ強制してしまったようですいませんでした。



この投稿にコメントする

削除パスワード

No.24254

Re:文字列で与えられた式の評価
投稿者---pseudo(2005/11/19 23:13:25)


重大なヒント:
「C言語による最新アルゴリズム事典」という良書があります。
その本に載っているソースコードは全て
http://www.vector.co.jp/soft/data/prog/se002453.html
からダウンロードが可能です。

さて・・・
本件,「再帰的下向き構文解析(再帰下降構文解析)」が解答となります。
あなたが評価したいのは「式」ですが・・・
 1. 「式」とは「項」そのものか,「項」を '+' か '-' で繋いだものである
 2. 「項」とは「因子」そのものか,「因子」を '*' か '/' で繋いだものである
 3. 「因子」とは「数」あるいは カッコで囲まれた「式」である
 4. 「数」とは,数字の並びである(頭にハイフンもあるかも・・・)
これを記号的に書くと
 expression := term | term '+' term | term '-' term
 term := factor | factor '*' factor | factor '/' factor
 factor := number | '(' expression ')'
 number := '-'? '0'〜'9'

さてさて,これを素直にコーディングすればよいのです。
例えば expression ならば・・・
int expression() {
  int x = term();  // 最初のtermを得る
  for (;;) { // term同士が + や - で繋がっている間,繰り返し
    if (next_input() == '+')
      x += term(); // term + term
    else if (next_input() == '-')
      x -= term(); // term - term
    else
      break;
  }
  return x;
}

後は,term, factor, numberの実装を頑張ってください。


この投稿にコメントする

削除パスワード

No.24255

Re:文字列で与えられた式の評価
投稿者---Blue(2005/11/20 02:41:09)


1+2+3-4・・・
見たいなのを解釈するために

> expression := term | term '+' term | term '-' term
> term := factor | factor '*' factor | factor '/' factor
はそれぞれ、正規表現を使って

expression := term [('+'|'-') term]*
term       := factor [('*'|'/') factor]*

としたほうがベターですね。



この投稿にコメントする

削除パスワード

No.24256

Re:文字列で与えられた式の評価
投稿者---Blue(2005/11/20 02:46:02)


てか、expressionのソースではそのように実装されていますね。


この投稿にコメントする

削除パスワード

No.24265

Re:文字列で与えられた式の評価
投稿者---かずま(2005/11/20 15:49:49)


>> expression := term | term '+' term | term '-' term
>> term := factor | factor '*' factor | factor '/' factor
> はそれぞれ、正規表現を使って
> 
> expression := term [('+'|'-') term]*
> term       := factor [('*'|'/') factor]*
> 
> としたほうがベターですね。

確かに、最初の定義では 1 + 2 + 3 が構文解析できません。
修正版の定義では、7 - 5 - 3 の構文解析はできますが、演算子が左結合か
右結合かを別に指定しないと、(7 - 5) - 3 なのか 7 - (5 - 3) なのかが
決まりません。

expression := term | expression '+' term | expression '-' term
term := factor | term '*' factor | term '/' factor

とすれば左結合だということを構文規則に含めることができます。
C の規格書や K&R2 にはそんな風に記述されています。



この投稿にコメントする

削除パスワード

No.24317

Re:文字列で与えられた式の評価
投稿者---だん(2005/11/22 18:23:16)


皆様、いろいろご回答ありがとうございます。

再帰下降構文解析で行きたいと思います。

以上、ありがとうございました。


この投稿にコメントする

削除パスワード

管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    ログ    タグ一覧