fc2ブログ



構文解析

2008.12.04 10:23  パソコン甲子園 2005

問題 パソコン甲子園2005 17 かしこい電卓

式を入力すると、その値を計算して出力し終了するプログラムを作成してください。

  • 式は数値、演算記号、かっこからなり、=で終わります。
  • 数値は常に1桁の数字とします。(おもしろくないので、この条件は省略します)
  • 演算記号は+,-,*,/ の4つで、それぞれ、加算、減算、乗算、除算を表します。
  • 四則演算の優先順位は通常の計算と同じとします。すなわち乗算・除算は加算・減算よりも優先され、 同じ優先順位なら左から計算が行われます。
  • 0での割り算は発生しないものとします。
  • 演算はすべて整数で行い、小数点以下切捨てとします。
  • 入力される式の長さは40文字以内とします。

入力例
3
4-2*3=
4*(8+4+3)=
((1+1-1)*123)+(2*3-10)/2+25=


出力例
-2
60
146


解説

以下のEBNF(表記が正しいかは微妙です)で定義された文法を、トップダウン構文解析法で、再帰的にパースします。詳しい解説は、10分で書ける、お手軽パーザーがとても参考になります。

expression = term { ('+'|'-') term }
term = factor { ('*'|'/') factor }
factor = '(' expression ')' | number
number = { digit }

EBNFは、言語を形式的に定義するための表記法で、文字列や数列等の生成規則によって定義されます。例えば、 上記の expression とは、term または term のあとに + または - を演算子とした term がいくつか繰り返されることを意味します。term の生成規則についても同様です。また、factor は ( ) で囲まれた expression または 数字 になります。 これらの規則を、それぞれ再帰関数により実装します。

サンプルプログラム

001 #include<iostream>
002 #include<string>
003 
004 using namespace std;
005 
006 int expression();
007 int term();
008 int factor();
009 
010 string exp;
011 int p;
012 
013 int expression(){
014     int value = term();
015     while( exp[p] == '+' || exp[p] == '-' ){
016         if ( exp[p] == '+' ) { p++; value += term(); }
017         else { p++; value -= term(); }
018     }
019     return value;
020 }
021 
022 int term(){
023     int value = factor();
024     while( exp[p] == '*' || exp[p] == '/' ){
025         if ( exp[p] == '*' ) { p++; value *= factor(); }
026         else { p++; value /= factor(); }
027     }
028     return value;
029 }
030 
031 int factor(){
032     int value = 0;
033     if ( exp[p] == '(' ){
034         p++; value = expression(); p++;
035     } else {
036         while( isdigit(exp[p]) ) { value = value*10 + exp[p++] - '0';}
037     }
038     return value;
039 }
040 
041 int main(){
042     int tcase; cin >> tcase;
043     for ( int i = 0; i < tcase; i++ ){
044         cin >> exp;
045         p = 0;
046         cout << expression() << endl;
047     }
048     return 0;
049 }
スポンサーサイト



テーマ : プログラミング - ジャンル : コンピュータ

| コメント(2) | トラックバック(0) | ↑ページトップ |

この記事へのコメント

ページの印刷時にソースコードがセンタリングされてしまい大変見づらいのですが,なんとかなりませんでしょうか.

_ | URL | 2008.12.23 03:40

Re: 印刷

ご指摘ありがとうございました。印刷時のセンタリングの不具合を修正しました。
他の記事についても順次修正していきます。

管理人 | URL | 2008.12.23 13:28 | 編集

コメントを書く


管理人にのみ表示

↑ページトップ

この記事へのトラックバック

この記事にトラックバックする(FC2ブログユーザー)

↑ページトップ