構文解析
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) | ↑ページトップ |