)
前言
「无括号四则运算器」要求解析只包含加、减、乘、除、整数和空格的表达式，按先乘除后加减、同级从左到右的规则求值。它比带括号的版本少了一层「括号递归」，但优先级、一元负号、多位数、除零这些边界一个都不少，是练习递归下降（recursive descent）的好题目。
常见误解有三类。第一，从左到右顺序扫描、遇到运算符就立刻计算，这样1 + 2 * 3会得到 9 而不是 7。第二，只读一位数字，遇到123只取1。第三，把一元负号当成二元减号处理，2 * -3在乘号后面遇到-时解析失败。
本文用递归下降实现：把表达式拆成「表达式 → 项 → 因子」三层，每层只处理自己那一级的运算符，优先级由调用层次天然保证。代码以 C++17 为准，使用long long做整数运算；文末会说明溢出与除零的处理边界。
一、文法与优先级
把表达式写成文法：
expr := term (('+' | '-') term)*
term := factor (('*' | '/') factor)*
factor := ('+' | '-')* number
number := digit+expr处理加减，term处理乘除，factor处理一元正负号和数字。调用关系是expr → term → factor，越往下优先级越高。每一层用循环处理「同级运算符」，因此同级运算符自然左结合：10 - 3 - 2先算10 - 3，再减 2，结果是 5，而不是10 - (3 - 2)。
这种结构的好处是：加括号只需要在factor里增加一条「遇到左括号就递归调用expr，再匹配右括号」的分支，其他层不用改。本文不实现括号，但保留这个扩展点。
数字可以有多位，解析时循环读取连续数字，用value = value * 10 + digit累加。空白字符在每一层读取前跳过，因此1+ 2 *3和1 + 2 * 3等价。空白只允许出现在记号之间，不能出现在数字中间（12 3会被解析成两个数，随后因缺少运算符而报错）。
二、递归下降的实现结构
用一个Parser类保存输入字符串的引用和当前下标pos_。每个解析函数都从pos_当前位置开始，读取自己负责的部分，并把pos_推进到下一个未处理字符。
parseExpr：
- 调用
parseTerm得到左值。 - 循环：跳过空白；若当前字符是
+或-，记录运算符并前进，调用parseTerm得到右值，执行加减；否则退出循环。 - 返回累计结果。
parseTerm与parseExpr同构，只是运算符换成*、/，调用的下层换成parseFactor。除法要先检查右值是否为 0；整数除法向零截断，-7 / 2得到 -3，这是 C++ 的规则，不要按数学上的「向下取整」理解。
parseFactor：
- 跳过空白。
- 若当前是
+或-，前进并递归调用自身，返回正/负结果。这允许--5、+-5这类写法。 - 否则必须是数字；循环读取连续数字，累加成整数。
- 若一个数字都没有，抛出解析错误。
最外层parse调用parseExpr后，还要跳过空白并检查pos_是否到达末尾。若还有剩余字符（例如1 + 2abc），说明输入非法，不能默默忽略。
三、边界：除零、溢出与非法字符
除零：整数除以 0 是未定义行为（undefined behavior, UB），必须在除法前检查。示例用异常报告错误，调用方捕获后打印提示。不要用「返回 0」掩盖错误，那会让1/0看起来像合法结果。
溢出：long long的加减乘都可能溢出，有符号溢出是 UB。示例在解析数字时检查了「乘 10 加 digit」是否超过LLONG_MAX，但运算符层面的溢出没有逐一检查，因此要求输入的中间结果落在long long范围内。生产代码若不能保证这一点，应改用大整数库，或在每次加减乘前做范围检查；不要依赖「溢出会回绕」这种未定义行为。另外，LLONG_MIN / -1也会溢出，示例单独拦截。
非法字符：数字解析失败、运算符后没有操作数、表达式末尾有多余字符，都应该报错。错误信息至少包含位置，方便定位。示例用std::runtime_error抛出，主函数捕获后输出。
空表达式：parseFactor在没有任何数字时抛错，因此空串、只有空白的串都会失败，不会返回 0。
一元负号与二元减号：2-3中的-由parseExpr处理；2*-3中的-出现在parseFactor开头，由一元分支处理。两者靠「当前位置在哪个解析层」区分，不需要额外的词法状态。
四、完整实现
// 适用于 C++17
#include <cctype>
#include <iostream>
#include <limits>
#include <stdexcept>
#include <string>
class Parser {
public:
explicit Parser(const std::string& text) : text_(text) {}
long long parse() {
const long long value = parseExpr();
skipSpaces();
if (pos_ != text_.size()) {
throw std::runtime_error("unexpected trailing characters");
}
return value;
}
private:
void skipSpaces() {
while (pos_ < text_.size() &&
std::isspace(static_cast<unsigned char>(text_[pos_]))) {
++pos_;
}
}
long long parseExpr() {
long long value = parseTerm();
for (;;) {
skipSpaces();
if (pos_ >= text_.size() ||
(text_[pos_] != '+' && text_[pos_] != '-')) {
break;
}
const char op = text_[pos_++];
const long long rhs = parseTerm();
value = (op == '+') ? value + rhs : value - rhs;
}
return value;
}
long long parseTerm() {
long long value = parseFactor();
for (;;) {
skipSpaces();
if (pos_ >= text_.size() ||
(text_[pos_] != '*' && text_[pos_] != '/')) {
break;
}
const char op = text_[pos_++];
const long long rhs = parseFactor();
if (op == '*') {
value *= rhs;
} else {
if (rhs == 0) {
throw std::runtime_error("division by zero");
}
if (value == std::numeric_limits<long long>::min() && rhs == -1) {
throw std::runtime_error("integer overflow");
}
value /= rhs;
}
}
return value;
}
long long parseFactor() {
skipSpaces();
if (pos_ < text_.size() && (text_[pos_] == '+' || text_[pos_] == '-')) {
const char sign = text_[pos_++];
const long long value = parseFactor();
return (sign == '-') ? -value : value;
}
if (pos_ >= text_.size() ||
!std::isdigit(static_cast<unsigned char>(text_[pos_]))) {
throw std::runtime_error("number expected");
}
long long value = 0;
while (pos_ < text_.size() &&
std::isdigit(static_cast<unsigned char>(text_[pos_]))) {
const int digit = text_[pos_] - '0';
if (value > (std::numeric_limits<long long>::max() - digit) / 10) {
throw std::runtime_error("number too large");
}
value = value * 10 + digit;
++pos_;
}
return value;
}
const std::string& text_;
std::size_t pos_ = 0;
};
int main() {
std::string line;
if (!std::getline(std::cin, line)) {
return 1;
}
try {
Parser parser(line);
std::cout << parser.parse() << '\n';
} catch (const std::exception& e) {
std::cout << "error: " << e.what() << '\n';
return 1;
}
return 0;
}按语法推演几个输入：1 + 2 * 3先由parseTerm读出 2、遇到*读出 3，得到 6，再由parseExpr加 1，结果是 7；10 - 3 - 2在parseExpr的循环里先算 7，再减 2，结果是 5；2 * -3 + 10在parseTerm中把-3作为因子，得到 -6，再加 10，结果是 4；10 / 3是整数除法，结果是 3；1 / 0在除法前抛异常。
代码中的加减乘没有做逐次溢出检查，这是有意的简化：完整检查会让示例膨胀一倍，而且需要处理LLONG_MIN的各种边界。文章已经把「中间结果必须在long long范围内」写成前提；若你的输入可能接近边界，必须在value + rhs、value - rhs、value * rhs之前加检查，不能假定溢出是安全的。
常见坑点
1. 从左到右直接求值
❌ 扫描到运算符就立刻用当前累计值计算，1 + 2 * 3得到 9。
✅ 分层解析，parseTerm先算乘除，parseExpr再算加减。
2. 只读一位数字
❌value = text_[pos_] - '0'; ++pos_;，123只得到 1。
✅ 用while读取连续数字，累加value * 10 + digit。
3. 不跳过空白
❌ 遇到空格就报「非法字符」。
✅ 每层读取前skipSpaces，并注意std::isspace的参数要转unsigned char。
4. 不支持一元负号
❌2 * -3在乘号后调用数字解析，直接失败。
✅ 在parseFactor开头处理+/-并递归。
5. 除法不检查零
❌value /= rhs;当rhs == 0时是 UB。
✅ 先判断rhs == 0并报错。
6. 忽略尾部多余字符
❌parseExpr返回后直接输出，1+2abc被当成 3。
✅ 解析完检查pos_ == text_.size()。
7. 把整数除法当浮点除法
❌ 认为7 / 2是 3.5。
✅ 整数相除向零截断；需要小数就改用double或定点表示。
8. 认为溢出会安全回绕
❌ 依赖long long溢出后的值做判断。
✅ 有符号溢出是 UB；加检查或改用大整数库。
总结
| 层次 | 负责 | 运算符 |
|---|
expr | 加减 | +、-，左结合 |
term | 乘除 | *、/，左结合 |
factor | 一元正负、数字 | +、-前缀 |
| 边界 | 处理 |
|---|
| 多位数 | 循环累加 |
| 空白 | 每层跳过 |
| 除零 | 除法前检查 |
| 尾部字符 | 解析后校验 |
| 溢出 | 解析检查 + 前提约束 |
无括号四则运算器的骨架就是三层递归下降：优先级高的层被优先级低的层调用，同级运算符用循环实现左结合。把「多位数、空白、一元符号、除零、尾部校验」这五个边界补上，表达式求值就不会在看起来简单的输入上出错。
