数式パーサ
ちょっと前に書いた数式パーサのプログラム.取り敢えず動けばいいという程度のコードです.Googleや本をほとんど見ずに数式パーサを書いてみよう,と思い書いてみたら自分でも何をやっているのかよくわからないコードになってしまいました.用語とかが正しいかは知りません.
コマンドラインの第一引数に数式を書いたテキストファイルを渡すと計算した結果を表示します.
整数と+-*/%^()と符号の-が使えます.
#include <iostream> #include <fstream> #include <vector> #include <sstream> #include <cstdlib> #include <cmath> #include <climits> using namespace std; //このプログラムで使う文字の一覧 const string USE_CHARACTERS("0123456789+-*/%^()"); //文字の種類 enum CHAR_TYPE { NUMBER, SYMBOL, LEFT_PARENTHESIS, RIGHT_PARENTHESIS, OTHER }; vector<string> split(const string script);//トークンに分割する関数 long long calc(vector<string> expression);//式を計算した結果を返す関数 CHAR_TYPE getCharType(const char s);//文字の種類を取得する関数 //演算子を探索して式を左右に分割しそれぞれを計算させる関数 long long searchAndSplit(vector<string> expression, vector<char> symbols, bool rpri/*右結合か?*/); //メイン関数。コマンドラインでファイル名を指定する int main(int argc, char* argv[]) { fstream file; if(argc < 2) { cout << "計算するファイルを指定してください。" << endl; } //ファイルを開く file.open(argv[1], ios::in); if(!file.is_open()) { cout << "ファイルの読み込みに失敗しました。" << endl; return 0; } //ファイルの内容を読み込む string script(""); while(!file.eof()) { string s; getline(file, s); script += s; } //ファイルを閉じる file.close(); //スペースや、数式には使用されない文字を削除する string use_characters(USE_CHARACTERS); for(int i = 0; i < script.length(); ++i) { int c; for(c = 0; c < use_characters.length(); ++c) { if(use_characters.at(c) == script.at(i)) break; } if(c == use_characters.length()) { script.erase(i, 1); --i; } } //計算して結果を表示 cout << calc(split(script)) << endl; return 0; } //トークンに分割する関数 vector<string> split(const string script) { vector<string> expression; string s(""); CHAR_TYPE reading_char = OTHER; for(int i = 0; i < script.length(); ++i) { if(getCharType(script.at(i)) == NUMBER && reading_char == NUMBER) { s += script.at(i); } else { if(reading_char != OTHER) { expression.push_back(s); } s = script.at(i); reading_char = getCharType(script.at(i)); } } expression.push_back(s); return expression; } //式を計算した結果を返す関数 long long calc(vector<string> expression) { //トークンの数が1ならintに直して返す if(expression.size() == 1) { istringstream istr(expression.at(0).data()); long long n; istr >> n; return n; } //符号としてのマイナスがあるのは式の最初だけと考えられるので先頭に0を追加 if(expression.at(0) == "-") { expression.insert(expression.begin(), string("0")); } else { //式全体が括弧で囲まれていたら外して再帰 if(getCharType(expression.at(0).at(0)) == LEFT_PARENTHESIS && getCharType(expression.at(expression.size() - 1).at(0)) == RIGHT_PARENTHESIS) { int nest_num = 0;//括弧のネストの深さ int outer_pnum = 0;//最も外側の括弧のペアの数 for(int i = 0; i < expression.size(); ++i) { if(getCharType(expression.at(i).at(0)) == LEFT_PARENTHESIS) { ++nest_num; } else if(getCharType(expression.at(i).at(0)) == RIGHT_PARENTHESIS) { --nest_num; if(nest_num == 0) ++outer_pnum; } } if(outer_pnum == 1) { expression.erase(expression.begin(), expression.begin() + 1); expression.pop_back(); return calc(expression);//再帰 } } } vector<char> s; long long result; s.push_back('+'); s.push_back('-'); if((result = searchAndSplit(expression, s, false)) != LLONG_MIN) return result; s.clear(); s.push_back('*'); s.push_back('/'); s.push_back('%'); if((result = searchAndSplit(expression, s, false)) != LLONG_MIN) return result; s.clear(); s.push_back('^'); if((result = searchAndSplit(expression, s, true)) != LLONG_MIN) return result; return LLONG_MIN; } //演算子を探索して式を左右に分割し計算する関数 long long searchAndSplit(vector<string> expression, vector<char> symbols, bool rpri/*右結合か?*/) { for(int i = ((rpri) ? 0 : expression.size() - 1); ((rpri) ? (i < expression.size()) : (0 <= i)); ((rpri) ? ++i : --i)) { for(int j = 0; j < symbols.size(); ++j) { //左右分割して再帰 if(expression.at(i).at(0) == symbols.at(j)) { vector<string> left_expression(i); for(int k = 0; k < i; ++k) { left_expression.at(k) = expression.at(k); } vector<string> right_expression(expression.size() - i - 1); for(int k = 0; k < expression.size() - i - 1; ++k) { right_expression.at(k) = expression.at(i + 1 + k); } long long left = calc(left_expression);//再帰 long long right = calc(right_expression);//再帰 switch(symbols.at(j)) { case '^': return static_cast<long long>(pow(static_cast<double>(left), static_cast<double>(right)));//値を返す case '*': return left * right; case '/': return left / right; case '%': return left % right; case '+': return left + right; case '-': return left - right; default: exit(EXIT_FAILURE); } } } if(getCharType(expression.at(i).at(0)) == ((rpri) ? LEFT_PARENTHESIS : RIGHT_PARENTHESIS)) { (rpri) ? ++i : --i; int pnum = 0; while(true) { if(getCharType(expression.at(i).at(0)) == ((rpri) ? LEFT_PARENTHESIS : RIGHT_PARENTHESIS)) { ++pnum; } if(getCharType(expression.at(i).at(0)) == ((rpri) ? RIGHT_PARENTHESIS : LEFT_PARENTHESIS)) { if(pnum == 0) break; --pnum; } (rpri) ? ++i : --i; } } } return LLONG_MIN; } //文字の種類を返す関数 CHAR_TYPE getCharType(const char s) { switch(s) { case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9': return NUMBER; case '+': case '-': case '*': case '/': case '%': case '^': return SYMBOL; case '(': return LEFT_PARENTHESIS; case ')': return RIGHT_PARENTHESIS; default: return OTHER; } }
演算子が連続したり括弧がきちんと対応していなかった場合は例外を吐いて落ちます.