Реализации алгоритмов/Алгоритм Рутисхаузера

Алгоритм Рутисхаузера — один из ранних формальных алгоритмов разбора выражений со скобками, его особенностью является предположение о правильной скобочной структуре выражения, также алгоритмом не учитывается неявный приоритет операции.

C++

std::string Rutishauser::eval(std::string expr){
    int levels[expr.length()];
    int level = 0;
    int maxl = 0;
    int maxs = 0;
    int j = 0;
    bool isInNum = false;
    // Расстановка уровней
    for(int i = 0; i < expr.length(); i++){
        if(!isInNum || !isNum(expr[i])){
            if((expr[i] == '(') || (isNum(expr[i]))){
                level++;
            }else if((expr[i] == ')') || (!isNum(expr[i]))){
                level--;
            }
            levels[j] = level;
            if(level > maxl){
                maxl = level;
                maxs = i;
            }
            j++;
        }
        if(isNum(expr[i])){
            isInNum = true;
        }else{
            isInNum = false;
        }
    }
    if(j == 1){
        return expr;
    }
    int c = 0;
    for(int i = 0; i < j; i++){
        if(levels[i] == maxl){
            c++;
        }
    }
    if(c % 2 != 0){
        for(int i = maxs; i < expr.length(); i++){
            if(!isNum(expr[i])){
                std::string sa, sb, sc;
                if(maxs > 1){
                    sa = expr.substr(0, maxs - 1);
                }
                if(i > maxs){
                    sb = expr.substr(maxs, i - maxs);
                }else{
                    sb = expr[maxs];
                }
                if(i < expr.length() - 1){
                    sc = expr.substr(i + 1, expr.length());
                }
                return Rutishauser::eval(sa + sb + sc);
            }
        }
    }
    bool isOp = false;
    int p = maxs;
    int p1 = maxs;
    int a, b;
    for(int i = maxs; i < expr.length(); i++){
        if(!isNum(expr[i])){
            if(isOp){
                p1 = i;
                break;
            }
            isOp = true;
            a = atoi(expr.substr(maxs, i - 1).c_str());
            p = i;
        }
    }
    b = atoi(expr.substr(p + 1, p1 - 1).c_str());
    int tmp = 0;
    switch(expr[p]){
        case('+'):
            tmp = a + b;
            break;
        case('-'):
            tmp = a - b;
            break;
        case('*'):
            tmp = a*b;
            break;
        case('/'):
            tmp = a/b;
            break;
    }
    return Rutishauser::eval(expr.substr(0, maxs) + IntToString(tmp) + expr.substr(p1, expr.length() - p1 + 1));
}