数学表达式计算器

今天闲来无事，使用C++写了一个数学表达式计算器，即输入一段包含数字、加减乘除（+、-、*、/）、括号（()）,输出计算的结果，例如输入：1+2*3+4，输出11。

代码中，并没有使用逆波兰式实现，之所以没用，是因为我希望遍历完整个字符串后，就能得到我期待的中间结果，最后使用中间结果进行加或减即可，以达到最大性能。其中，中间结果可能是表达式中算法的积或者商，或者括号中的子表达式计算出来的结果。因为存在子表达式，所以使用递归算法来计算出子表达式的结果。无论怎么样，我的目的，不希望多次遍历字符串，只希望遍历一次字符串，但是遍历过程中只是计算出来中间结果，所以使用到栈这个数据结构来存储中间结果，等遍历完整个字符串后，就得到所有的中间结果，最后从栈中弹出中间结果计算出最终结果。

整体来看，有效代码，大概150行左右，不包括测试代码，感觉还可以优化更简洁写，然后异常的话，兼容类似，-1+2、-1+2+-3，即数字前面可以有+/-表示正数还是负数，还有允许前后，中间有空格（' '、'\n'、'\t'），-1+2+-3+4 4，这个4 4按44来处理，还有就是不支持除以0。

最后，再说下，为什么想写这个。一个觉得有趣，一个觉得看看一次遍历字符串结合状态机能不能很好的完成这件事情，目前来看，虽然代码简洁性、程序健壮性还有优化空间，但目的达到了，这里更像给大家，希望能帮助到有需要的小朋友。如若您觉得对您有帮助，谢谢点击上您的小爱心，您的鼓励是我的动力，谢谢。然后这里再提一下，下一次，我还想写一个类似遍历字符串就完成解析工作的代码，可能是解析http请求、可能是解析c语言源代码、可能是解析html，可能是解析elf二进制格式，我内心最感兴趣的是些解析c语言源代码的，但是刚觉空闲时间也就可能只能解析出中间结果，至于运行还需要更多空闲时间，要解决运行时考虑的相互引用问题，需要的时间就更多，这个挑战就更大啦，不过没挑战，也没写的兴趣。所以，还没决定好，敬请期待啦～

所有代码如下：包括测试代码，全部放在一个文件：

/**
 * Expression calculator
 * @Author Rizhong Li<lirizhong97@163.com>
 * @Date 2024-01-09
 */

#include <iostream>
#include <string>
#include <stack>
#include <algorithm>

using namespace std;

typedef enum em_op_type_t { OP_NONE, OP_PLUS, OP_MINUS, OP_MULTI, OP_DIV, } op_type_t;
typedef enum em_token_type_t { TOKEN_NUM, TOKEN_OP } token_type_t;
typedef struct st_num_t { long double num; int ok; } num_t;
typedef struct st_op_t { op_type_t op; } op_t;

void trim_left(char *&ps, char *&pe);
void trim_right(char *&ps, char *&pe);
num_t evaluate(const string& expr);
num_t expect_num(const string& expr, char *&ps, char *&pe);
op_t expect_op(char *&ps, char *&pe);

void trim_left(char *&ps, char *&pe) {
    while (ps <= pe && isspace(*ps)) ++ps;
}

void trim_right(char *&ps, char *&pe) {
    while (pe >= ps && isspace(*pe)) --pe;
}

num_t expect_num(const string& expr, char *&ps, char *&pe) {
    trim_left(ps, pe);
    if (ps > pe) {
        return {0, -1};
    }

    double sign = 1;
    if (ps[0] == '-' || ps[0] == '+') {
        ps++;
        sign = -1;
    }

    if (ps[0] == '(') {
        char *s = ps;
        char *e = ps;
        while (ps <= pe) {
            if (ps[0] == ')') {
                e = ps;
            } else {
                if (ps == pe) e = pe;
            }
            ps++;
            if (s != e) {
                string tmp_expr(expr,s - expr.c_str()+1, e - s-1);
                num_t num = evaluate(tmp_expr);
                num.num *= sign;
                return num;
            }
        }
    } else {
        string token;
        while (ps <= pe) {
            trim_left(ps, pe);
            if (ps > pe) break;
            if (std::isdigit(ps[0]) || ps[0] == '.') {
                token += ps[0];
            } else {
                break;
            }
            ps++;
        }

        if (!token.empty()) {
            try {
                return {sign * std::stold(token), 0};//Fixme: maybe overflow
            } catch (...) {
                return {0, -1};
            }
        }
    }

    return {0, -1};
}

op_t expect_op(char *&ps, char *&pe) {
    trim_left(ps, pe);
    if (ps > pe) return {OP_NONE};
    char op = ps[0];
    ps++;
    switch (op) {
        case '+': return {OP_PLUS};
        case '-': return {OP_MINUS};
        case '*': return {OP_MULTI};
        case '/': return {OP_DIV};
    }
    return {OP_NONE};
}

num_t evaluate(const string& expr) {
    num_t res = {0, false};
    char *ps = (char *)expr.c_str();
    char *pe = (char *)expr.c_str() + expr.length() - 1;
    token_type_t state = TOKEN_NUM;
    stack<op_t> ops;
    stack<num_t> nums;

    trim_left(ps, pe);
    trim_right(ps, pe);
    if (ps > pe) {
        return res;
    }

    while (ps <= pe) {
        switch (state) {/* state machine */
            case TOKEN_NUM: {
                num_t num = expect_num(expr, ps, pe);
                if (num.ok) return res;
                nums.push(num);
                state = TOKEN_OP;
                break;
            }
            case TOKEN_OP: {
                op_t op = expect_op(ps, pe);
                if (op.op == OP_NONE) return res;
                if (op.op == OP_PLUS || op.op == OP_MINUS) {
                    ops.push(op);
                    state = TOKEN_NUM;
                } else {
                    num_t num = expect_num(expr, ps, pe);
                    if (num.ok) return res;
                    if (nums.size() <= ops.size()) return res;
                    num_t mid = nums.top();
                    nums.pop();
                    if (op.op == OP_MULTI) {
                        mid.num *= num.num;
                    } else {
                        if (num.num == 0) return res;
                        mid.num /= num.num;
                    }
                    nums.push(mid);
                    state = TOKEN_OP;
                }
                break;
            }
        }
    }

    while (ops.size() > 0) {
        op_t op = ops.top();
        ops.pop();

        num_t n1 = nums.top();
        nums.pop();
        num_t n2 = nums.top();
        nums.pop();

        if (op.op == OP_PLUS) {
            n2.num += n1.num;
        } else if (op.op == OP_MINUS) {
            n2.num -= n1.num;
        }
        if (ops.empty()) {
            res.num += n2.num;
        } else {
            nums.push(n2);
        }
    }

    if (ops.empty() && nums.empty()) {
        res.ok = 0;
    }

    return res;
}

int main() {
     string exprs[] = {
     " \t \n  \t \n ",
     " \t \n-1234+5678-7890*1/2\t \n \n",
     " \t \n-1234+-5678-7890*1/2\t \n \n",
     " \t \n-1234+-5678--7890*1/2\t \n \n",
     " \t \n-1234+-5678--7890*1./2.0+.1\t \n \n",
     " \t \n-1234+-(5678.3--7890)*1./(2.0+.1)\t \n \n",
     " \t \n-1234+-(5678.3--7890)*1./(2.0+.1)/0\t \n \n",
     " \t \n-1234+-(5678.3--7890)*1./(2.0+.1)/1\t \n \n"
     };

    for (const auto& expr : exprs) {
        try {
            num_t res = evaluate(expr);
            cout << "[" << expr << "]:[" << (res.ok == 0? "ok" : "nok") << "][" << res.num << "]" << endl;
        } catch (const exception& e) {
            cout << "[" << expr << "]:[nok][Error: " << e.what() << "]" << endl;
        }
    }

    return 0;
}

输出的结果为：

[ 	 
  	 
 ]:[ok][0]
[-1+2]:[ok][1]
[-1+2+-3]:[ok][-2]
[-1+2+-3+4 4]:[ok][42]
[--1+2+-3+4 4]:[ok][0]
[ 	 
-1234+5678-7890*1/2	 
 
]:[ok][499]
[ 	 
-1234+-5678-7890*1/2	 
 
]:[ok][-10857]
[ 	 
-1234+-5678--7890*1/2	 
 
]:[ok][-2967]
[ 	 
-1234+-5678--7890*1./2.0+.1	 
 
]:[ok][-2967.1]
[ 	 
-1234+-(5678.3--7890)*1./(2.0+.1)	 
 
]:[ok][-7695.1]
[ 	 
-1234+-(5678.3--7890)*1./(2.0+.1)/0	 
 
]:[ok][0]
[ 	 
-1234+-(5678.3--7890)*1./(2.0+.1)/1	 
 
]:[ok][-7695.1]