UVa 10614 Dreadful Vectors

题目描述

$\text{Tanzir}$ 和 $\text{Taufiq}$ 设计了一个向量计算电路，但电路对非法输入十分敏感，曾经因为一个错误的输入字符串导致整个实验室爆炸。现在他们需要一个程序来预测输入字符串的计算结果，避免再次发生灾难。

在本题中，标量定义为整数，向量定义为三个标量表达式组成的元组，用方括号 [ 和 ] 括起，元素之间用逗号 , 分隔。表达式支持以下运算：

• 加法 + 和减法 -：要求两个操作数同为标量或同为向量，结果类型与操作数相同。
• 乘法 *：允许任意混合。当两个操作数都是向量时，表示点积（结果为标量）；否则表示标量乘法（标量乘向量得向量，标量乘标量得标量）。
• 叉积 x：仅限两个向量之间运算，结果为向量。

运算优先级遵循常规代数规则：括号优先级最高；乘法和叉积优先级相同且高于加减法；同优先级运算从左到右结合。

输入格式

输入包含若干行，每行一个表达式字符串，长度不超过 $100$。字符串可包含空格、数字、运算符 +、-、*、x、分隔符 ,、括号 (、)、方括号 [、]。所有其他字符均为非法。

整数均为非负整数，但中间结果和最终结果可能为负。所有标量值的绝对值小于 $2^{31}$。

输入以单独一行 # 结束。

输出格式

对于每个表达式，若无错误，输出计算结果：

• 若结果为标量，直接输出整数。
• 若结果为向量，输出 [x,y,z] 形式（不含空格）。

若有任何错误（非法字符、语法错误、类型不匹配、数字中间有空格等），输出 Bang!。

样例

输入

[1,2,3] + [4,5,6]
[1,2,3] * ( [4,15,6] * (2- 1*1) )
1,2,3] x [4,5,6] x 2
[1,2,3,4+5]
#

输出

[5,7,9]
52
Bang!
Bang!

题目分析

本题的核心是实现一个表达式求值器，支持标量和向量的混合运算，并处理各种可能的错误输入。

难点一：词法分析的复杂性

输入字符串可能包含空格，空格的位置影响合法性。尤其是数字中间的空格属于非法（如 12 34），而数字前后的空格是允许的。这要求我们在解析数字时，必须检查数字字符串内部是否含有空格。

难点二：类型系统的动态判断

表达式的类型（标量或向量）在运行时才能确定。标量与向量之间的加法、减法属于类型错误，而乘法则允许混合。我们需要在求值过程中动态维护每个子表达式的类型。

难点三：运算符优先级和结合性

表达式包含四种运算符，优先级分为两级：

• 第一级：* 和 x（左结合）
• 第二级：+ 和 -（左结合）

括号可以改变优先级。这要求我们实现一个能够正确处理优先级的解析器。

解题思路

整体框架：递归下降解析

采用递归下降解析方法，按照优先级构建语法树。每个解析函数对应一个优先级层次，通过互相调用来实现优先级规则。

定义三个核心解析函数：

• parseAddExpr()：处理加减法（最低优先级）
• parseMulExpr()：处理乘法和叉积（中间优先级）
• parsePrimary()：处理原子表达式（最高优先级），包括数字、向量、括号表达式

空格处理策略

为了避免空格干扰解析，设计统一的空格跳过机制：

• skipSpaces()：从当前位置开始，跳过所有连续空格。
• peek()：跳过前导空格后返回当前字符。
• get()：跳过前导空格后返回当前字符，并将位置指针后移。

所有解析函数在读取字符前都通过 peek() 或 get() 跳过空格，这样数字前后的空格被自动忽略。

数字解析与空格检测

数字解析需要额外处理数字内部空格的检测：

int parseNumber() {
if (!isDigit(peek())) { errorFlag = true; return 0; }
int num = 0;
while (isDigit(peek())) {
num = num * 10 + (get() – '0');
}
return num;
}

由于 peek() 和 get() 会跳过空格，数字内部的空格实际上会导致解析提前终止，从而被后续的语法检查捕获。但为了更早地检测并报告错误，可以在解析前进行一次预扫描：

bool hasSpaceInNumber(const string& s) {
for (int i = 0; i < s.size(); i++) {
if (isdigit(s[i])) {
int j = i;
while (j < s.size() && isdigit(s[j])) j++;
int k = j;
while (k < s.size() && s[k] == ' ') k++;
if (k < s.size() && isdigit(s[k])) return true;
i = j;
}
}
return false;
}

该函数检测 "12 34" 这种模式：一个数字结束后有空格，且空格后面紧跟着另一个数字。

表达式求值机制

每个解析函数返回一个 Expr 结构体，包含：

• isVec：标识该表达式是标量（false）还是向量（true）
• val：当为标量时存储整数值
• vec：当为向量时存储三个分量

运算过程中，根据操作数的类型组合，执行对应的运算，并更新结果类型。

以乘法为例：

• 标量 $\times$ 标量：结果为标量（整数乘法）
• 标量 $\times$ 向量：结果为向量（各分量乘以标量）
• 向量 $\times$ 标量：同标量乘向量
• 向量 $\times$ 向量：结果为标量（点积）

叉积则要求两个操作数都是向量，结果为向量。

加减法要求两个操作数类型相同，结果类型不变。

错误传播

一旦检测到任何错误（非法字符、数字内嵌空格、语法错误、类型不匹配），设置 errorFlag = true，并在所有后续解析函数中提前返回，避免产生无效结果。

最终检查表达式是否被完全解析（即指针已到达字符串末尾），若有剩余字符则也视为错误。

复杂度分析

• 每个表达式长度不超过 $100$，解析过程为单趟扫描，时间复杂度 $O(L)$，其中 $L$ 为表达式长度。
• 空间复杂度 $O(1)$（不计输入存储）。

代码实现

// Dreadful Vectors
// UVa ID: 10614
// Verdict: Accepted
// Submission Date: 2026-06-10
// UVa Run Time: 0.000s
//
// 版权所有（C）2026，邱秋。metaphysis # yeah dot net

#include <bits/stdc++.h>
using namespace std;

struct Vector {
int x, y, z;
Vector(int x = 0, int y = 0, int z = 0) : x(x), y(y), z(z) {}
Vector operator+(const Vector& o) const { return Vector(x + o.x, y + o.y, z + o.z); }
Vector operator–(const Vector& o) const { return Vector(x – o.x, y – o.y, z – o.z); }
int operator*(const Vector& o) const { return x * o.x + y * o.y + z * o.z; } // 点积
Vector operator^(const Vector& o) const { return Vector(y * o.z – z * o.y, z * o.x – x * o.z, x * o.y – y * o.x); } // 叉积
Vector operator*(int k) const { return Vector(x * k, y * k, z * k); }
};

struct Expr {
bool isVec;
int val;
Vector vec;
Expr(int v) : isVec(false), val(v) {}
Expr(Vector v) : isVec(true), vec(v) {}
};

class Parser {
string s;
int p;
bool err;

void skip() { while (p < s.size() && s[p] == ' ') p++; }
char peek() { skip(); return p < s.size() ? s[p] : 0; }
char get() { skip(); return p < s.size() ? s[p++] : 0; }
bool isNum(char c) { return c >= '0' && c <= '9'; }

int readNum() {
if (!isNum(peek())) { err = true; return 0; }
int x = 0;
while (isNum(peek())) x = x * 10 + (get() – '0');
return x;
}

Expr primary() {
char c = peek();
if (c == '(') {
get();
Expr e = expr();
if (err) return Expr(0);
if (peek() != ')') err = true;
else get();
return e;
}
if (c == '[') {
get();
Expr x = expr();
if (err || x.isVec) { err = true; return Expr(0); }
if (peek() != ',') { err = true; return Expr(0); }
get();
Expr y = expr();
if (err || y.isVec) { err = true; return Expr(0); }
if (peek() != ',') { err = true; return Expr(0); }
get();
Expr z = expr();
if (err || z.isVec) { err = true; return Expr(0); }
if (peek() != ']') { err = true; return Expr(0); }
get();
return Expr(Vector(x.val, y.val, z.val));
}
if (isNum(c)) return Expr(readNum());
err = true;
return Expr(0);
}

Expr mul() {
Expr left = primary();
if (err) return Expr(0);
while (true) {
char op = peek();
if (op == '*') {
get();
Expr right = primary();
if (err) return Expr(0);
if (!left.isVec && !right.isVec) left = Expr(left.val * right.val);
else if (!left.isVec && right.isVec) left = Expr(right.vec * left.val);
else if (left.isVec && !right.isVec) left = Expr(left.vec * right.val);
else left = Expr(left.vec * right.vec);
}
else if (op == 'x') {
get();
Expr right = primary();
if (err) return Expr(0);
if (!left.isVec || !right.isVec) { err = true; return Expr(0); }
left = Expr(left.vec ^ right.vec);
}
else break;
}
return left;
}

Expr expr() {
Expr left = mul();
if (err) return Expr(0);
while (true) {
char op = peek();
if (op == '+' || op == '-') {
get();
Expr right = mul();
if (err) return Expr(0);
if (left.isVec && right.isVec) left = Expr(op == '+' ? left.vec + right.vec : left.vec – right.vec);
else if (!left.isVec && !right.isVec) left = Expr(op == '+' ? left.val + right.val : left.val – right.val);
else { err = true; return Expr(0); }
}
else break;
}
return left;
}

public:
Parser(const string& str) : s(str), p(0), err(false) {}
Expr parse() {
Expr res = expr();
if (err) return Expr(0);
skip();
if (p != s.size()) err = true;
return res;
}
bool hasErr() { return err; }
};

bool hasIllegal(const string& s) {
for (char c : s) if (c != ' ' && !isdigit(c) && c != '+' && c != '-' && c != '*' && c != 'x' && c != ',' && c != '[' && c != ']' && c != '(' && c != ')') return true;
return false;
}

bool spaceInNum(const string& s) {
for (int i = 0; i < s.size(); i++) {
if (isdigit(s[i])) {
int j = i;
while (j < s.size() && isdigit(s[j])) j++;
int k = j;
while (k < s.size() && s[k] == ' ') k++;
if (k < s.size() && isdigit(s[k])) return true;
i = j;
}
}
return false;
}

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string line;
while (getline(cin, line) && line != "#") {
if (hasIllegal(line) || spaceInNum(line)) { cout << "Bang!" << endl; continue; }
Parser parser(line);
Expr res = parser.parse();
if (parser.hasErr()) cout << "Bang!" << endl;
else if (res.isVec) cout << "[" << res.vec.x << "," << res.vec.y << "," << res.vec.z << "]" << endl;
else cout << res.val << endl;
}
return 0;
}

总结

本题的核心考点包括：

本题的代码虽然在长度上可以进一步精简（如使用运算符重载简化向量运算），但核心逻辑清晰，便于理解表达式的解析与求值过程。掌握递归下降解析方法，对于处理各种表达式求值问题具有普遍的指导意义。