四則演算の構文解析

expr_parser.cpp

// 四則演算の構文解析
// http://algorithms.blog55.fc2.com/blog-entry-154.html
// http://www.prefield.com/algorithm/string/parser.html
// を見ながら書いてみた．

#include <iostream>
#include <string>
using namespace std;
typedef pair<int, int> result;
#define value first
#define end second

result expr(int start, string& str);
result term(int start, string& str);
result factor(int start, string& str);
result number(int start, string& str);

result expr(int start, string& str) {
    result r = term(start, str);
    while (str[r.end] == '+' || str[r.end] == '-') {
        if (str[r.end] == '+') {
            result next_r = term(r.end+1, str);
            r.value += next_r.value;
            r.end   = next_r.end;
        } else if (str[r.end] == '-') {
            result next_r = term(r.end+1, str);
            r.value -= next_r.value;
            r.end   = next_r.end;
        }
    }
    return r;
}

result term(int start, string& str) {
    result r = factor(start, str);
    while (str[r.end] == '*' || str[r.end] == '/') {
        if (str[r.end] == '*') {
            result next_r = term(r.end+1, str);
            r.value *= next_r.value;
            r.end   = next_r.end;
        } else if (str[r.end] == '/') {
            result next_r = term(r.end+1, str);
            r.value /= next_r.value;
            r.end   = next_r.end;
        }
    }
    return r;
}

result factor(int start, string& str) {
    if (str[start] == '(') {
        result r = expr(start+1, str);
        r.end += 1;
        return r;
    } else {
        return number(start, str);
    }
}

result number(int start, string& str) {
    int ret = 0;
    while (isdigit(str[start])) {
        ret = ret*10 + str[start++] - '0';
    }
    return result(ret, start);
}

int main(void) {
    string str = "((1+1-1)*123)+(2*3-10)/2+25";
    cout << expr(0, str).value << endl;
}