3 * (4 + 5)
を27と解釈することです。ここでは演算は加減乗のみです。
3 * 4E-2
なら、
"3", "*", "4E-2"
と分割します。
<数値> ::= <整数>|<小数>|<浮動小数点数>
<整数> ::= <非負整数>|<負の整数>
<非負整数> ::= <数字>|<数字><数字>
<数字> ::= 0|1|…|9
<負の整数> ::= -<非負整数>
<小数> ::= <整数>.|<小数><整数>
<浮動小数点数> ::= <仮数><指数>
<仮数> ::= <整数>|<小数>
<指数> ::= E<整数>|E+<非負整数>|e<整数>|e+<非負整数>
とします（こういう書き方でよかったかな）。
分解は次のように前から一文字ずつ見ていきます。
まず、スペースとタブがだったら無視して次へ。
'('だったら'('を格納して次へ。
数字だったら、まだ数値が確定していないのでとりあえず数字をバッファに入れて、
「整数の次」というモードになります。
"."だったら、バッファに入れて
「次に数字が続くはずの小数」モードになります。
その他ならフォーマットエラーです。
このように今のモードに対して次の文字によって場合分けして文字や数値を格納し、
モードを移動していきます。
格納は次のようなToken構造体のリストに対して行います。
typedef struct {
char c;
double v;
} Token;
"("とか"+"は文字としてcに格納します。
数値の場合はcに'\0'を代入して、数値をvに格納します。
typedef list<Token> Tokens;
という形になります。
Tokens decompose(const string& str) {
Tokens result;
Token t;
string tmp;
char buff[2];
buff[1] = '\0';
int mode = 0;
string::const_iterator p;
for(p = str.begin(); p != str.end(); ++p) {
char c;
c = buff[0] = *p;
switch(mode) {
case 0: //initial
switch(c) {
case ' ': case '\t':
break;
case '(':
t.c = c;
result.push_back(t);
break;
case '0': case '1': case '2': case '3': case '4':
case '5': case '6': case '7': case '8': case '9':
tmp = buff;
mode = 2;
break;
case '+': case '-':
tmp = buff;
mode = 1;
break;
case '.':
tmp = buff;
mode = 3;
break;
default:
result.clear();
return result;
}
break;
case 1: //'+' or '-'
switch(c) {
case '(':
t.c = *(tmp.c_str());
result.push_back(t);
t.c = c;
result.push_back(t);
tmp = "";
mode = 10;
break;
case '0': case '1': case '2': case '3': case '4':
case '5': case '6': case '7': case '8': case '9':
tmp += c;
mode = 2;
break;
case '.':
tmp += c;
mode = 3;
break;
default:
result.clear();
return result;
}
break;
case 2: //integer
switch(c) {
case ' ' : case '\t':
t.c = '\0';
t.v = atof(tmp.c_str());
result.push_back(t);
tmp = "";
mode = 9;
break;
case ')':
t.c = '\0';
t.v = atof(tmp.c_str());
result.push_back(t);
t.c = c;
result.push_back(t);
tmp = "";
mode = 9;
break;
case '+': case '-': case '*':
t.c = '\0';
t.v = atof(tmp.c_str());
result.push_back(t);
t.c = c;
result.push_back(t);
tmp = "";
mode = 10;
break;
case '0': case '1': case '2': case '3': case '4':
case '5': case '6': case '7': case '8': case '9':
tmp += c;
break;
case '.':
tmp += buff;
mode = 5;
break;
case 'E': case 'e':
tmp += buff;
mode = 6;
break;
default:
result.clear();
return result;
}
break;
case 3: //('+' or '-') + '.'
switch(c) {
case '0': case '1': case '2': case '3': case '4':
case '5': case '6': case '7': case '8': case '9':
tmp += buff;
mode = 5;
break;
default:
result.clear();
return result;
}
break;
case 5: //decimal
switch(c) {
case ' ' : case '\t':
t.c = '\0';
t.v = atof(tmp.c_str());
result.push_back(t);
tmp = "";
mode = 9;
break;
case ')':
t.c = '\0';
t.v = atof(tmp.c_str());
result.push_back(t);
t.c = c;
result.push_back(t);
tmp = "";
mode = 9;
break;
case '+': case '-': case '*':
t.c = '\0';
t.v = atof(tmp.c_str());
result.push_back(t);
t.c = c;
result.push_back(t);
tmp = "";
mode = 10;
break;
case '0': case '1': case '2': case '3': case '4':
case '5': case '6': case '7': case '8': case '9':
tmp += buff;
break;
case 'E': case 'e':
tmp += buff;
mode = 6;
break;
default:
result.clear();
return result;
}
break;
case 6: //decimal + 'E' or 'e'
switch(c) {
case '+': case '-':
tmp += buff;
mode = 7;
break;
case '0': case '1': case '2': case '3': case '4':
case '5': case '6': case '7': case '8': case '9':
tmp += buff;
mode = 8;
break;
default:
result.clear();
return result;
}
break;
case 7: //decimal + 'E' or 'e' + '+' or '-'
switch(c) {
case '0': case '1': case '2': case '3': case '4':
case '5': case '6': case '7': case '8': case '9':
tmp += buff;
mode = 8;
break;
default:
result.clear();
return result;
}
break;
case 8: //floating point decimal
switch(c) {
case ' ': case '\t':
t.c = '\0';
t.v = atof(tmp.c_str());
result.push_back(t);
tmp = "";
mode = 9;
break;
case ')':
t.c = '\0';
t.v = atof(tmp.c_str());
result.push_back(t);
t.c = c;
result.push_back(t);
tmp = "";
mode = 9;
break;
case '+': case '-': case '*':
t.c = '\0';
t.v = atof(tmp.c_str());
result.push_back(t);
t.c = c;
result.push_back(t);
tmp = "";
mode = 10;
break;
case '0': case '1': case '2': case '3': case '4':
case '5': case '6': case '7': case '8': case '9':
tmp += buff;
break;
default:
result.clear();
return result;
}
break;
case 9: //waiting for operator
switch(c) {
case ' ': case '\t':
break;
case ')':
t.c = c;
result.push_back(t);
break;
case '+': case '-': case '*':
t.c = c;
result.push_back(t);
tmp = "";
mode = 10;
break;
default:
result.clear();
return result;
}
break;
case 10: //waiting for next number
switch(c) {
case ' ' : case '\t':
break;
case '(':
t.c = c;
result.push_back(t);
break;
case '0': case '1': case '2': case '3': case '4':
case '5': case '6': case '7': case '8': case '9':
tmp = buff;
mode = 2;
break;
case '.':
tmp = buff;
mode = 3;
break;
default:
result.clear();
return result;
}
break;
default:
break;
}
}
//post process
switch(mode) {
case 2: case 5: case 8:
t.c = '\0';
t.v = atof(tmp.c_str());
result.push_back(t);
break;
case 1: case 3: case 6: case 7: case 10:
result.clear();
return result;
default:
break;
}
//check pairness of parentheses
int lparen = 0;
for(Tokens::const_iterator p = result.begin(); p != result.end(); ++p) {
if(p->c == '(')
lparen++;
else if(p->c == ')')
if(--lparen < 0) {
result.clear();
return result;
}
}
if(lparen > 0)
result.clear();
return result;
}
う〜ん、長いですね。本当にこんなにコードが必要なんでしょうか。
あと、チェックが甘くて、
本来ならフォーマットエラーでも受け入れちゃっていることがあるかもしれません。
ちなみにフォーマットエラーの場合は、要素の無いlistが返ります。
カッコ ＞ 乗算 ＞ 加減算
なのでその順に演算していきます。
double calc(Tokens& v, Tokens::iterator first, Tokens::iterator last) {
Tokens::iterator p, p1, p2;
for(p = first; p != last; ++p) {
if(p->c == '(') {
p1 = p2 = p;
int lparen = 1;
for(++p2; p2 != last; ++p2) {
if(p2->c == '(')
lparen++;
else if(p2->c == ')') {
if(--lparen == 0) {
double d = calc(v, ++p1, p2);
v.erase(p1, ++p2);
p->c = '\0';
p->v = d;
break;
}
}
}
}
}
for(p = first; p != last; ++p) {
if(p->c == '*') {
p2 = p;
p1 = --p; ++p2;
double d = p1->v * p2->v;
v.erase(++p1, ++p2);
p->v = d;
}
}
double result = 0;
int mode = 0;
for(p1 = first; p1 != last; ++p1) {
switch(p1->c) {
case '+':
mode = 0;
break;
case '-':
mode = 1;
break;
case '\0':
if(mode == 0)
result += p1->v;
else
result -= p1->v;
break;
default:
cerr << "format error." << endl;
exit(1);
}
}
return result;
}
STLのlistって初めて使ったんだけど、こういう風でいいんですかね。
なにかしっくりこないんですが。
自分でリストを作ったほうがいいような。
calc.cpp
式を入力して2回Enterを押すと答えが出てきます。次回はこれを元に多項式を解釈します。