用记号类别状态机校验中缀表达式，再经调度场算法转后缀、用操作数栈求值；任一环节非法输出 NO。
OJ: roj
题目 ID: 1358
难度:普及-
标签:栈表达式求值字符串python
创建: 2026-09-30 06:50
更新: 2026-10-07 13:50
前置题目
roj 1331【例1-2】后缀表达式的值B 把 A 教的后缀表达式栈式归约（先弹右再弹左）当作流水线最后一段直接复用，代码里 eval_postfix 的 rhs,lhs=stack.pop(),stack.pop() 就是 A 的 eval 那一步，只是前面多叠了状态机校验和调度场转后缀；B 总结也自认「[[roj/1331]] 正是这条链路的后半段」。roj 1354括弧匹配检验A 教的「中途弹空（右括号多余）与扫完栈非空（左括号多余）两类失败点即配对非法」正是 B 的 tokenize 合法性子过程用的那一步（代码 depth==0 拒右括号、结束后 depth 非 0 拒），B 只把它简化成单类型计数器再叠加记号类别状态机、调度场转后缀与操作数栈求值。luogu P1739表达式括号匹配B 的 tokenize 合法性子过程直接沿用 A 教的「单计数器记录未匹配左括号、过程中不得为负、末尾归零」这一配对判定（代码里的 depth：expect_operand 位置遇 ) 而 depth==0 判 NO，扫描结束 depth 非 0 判 NO），只在此之上叠加记号类别状态机、调度场转后缀与操作数栈求值。
题目描述
输入一个以 @ 结束的中缀表达式（运算数为 0-9 组成的整数，可带一元负号 -；运算符有 + - * /；含小括号），判断它是否合法：不合法输出 NO，合法则转成后缀形式并用栈求出结果（整数除法向零取整）。
输入格式：一行以 @ 结束的字符串。输出格式：合法时输出一行整数，否则输出一行 NO。样例输入 1+2*8-9@，样例输出 8。
思路
用「当前位置该出现运算数还是运算符」一个状态校验合法性：运算数位只接受数字、( 和一元负号（-4、2*-3 合法），运算符位只接受二元运算符和 )，配合 depth 判括号配对，非法即输出 NO。合法时用调度场算法把中缀记号按优先级转成后缀，再用一个操作数栈从左到右归约求值，三步各扫描一遍，复杂度
参考代码
Python 版：
python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 06:55
# update_at: 2026-09-30 06:55
import sys
from operator import add, mul, sub
LEV = {'+': 1, '-': 1, '*': 2, '/': 2} # 二元运算符优先级，调度场算法弹栈用
APPLY = {'+': add, '-': sub, '*': mul} # 除法单独走分支：要向零取整并判除数为 0
def divide(a: int, b: int) -> int:
"""整数除法向零取整，与 C++ 的 int / int 一致（Python 的 // 是向下取整）。"""
quotient = abs(a) // abs(b)
return -quotient if (a < 0) != (b < 0) else quotient
def tokenize(expr: str) -> list[str] | None:
"""把中缀表达式切成记号并校验合法性；非法时返回 None。
校验只靠“当前位置该出现哪类记号”一个状态：操作数位只接受数字、左括号和
一元负号 '-'（直接并入后面的数字），运算符位只接受二元运算符和右括号。
连续两个运算符、空括号、头尾运算符、括号不配对，都会落到不该出现的位置上。
"""
tokens: list[str] = []
expect_operand = True # 下一个记号应当是操作数
depth = 0 # 尚未闭合的左括号个数
i = 0
while i < len(expr):
ch = expr[i]
if ch.isdigit() or (ch == '-' and expect_operand):
negative = ch == '-' # 操作数位上的 '-' 是负数标志
if negative:
i += 1
if i >= len(expr) or not expr[i].isdigit():
return None # 一元负号后面必须紧跟数字
j = i
while j < len(expr) and expr[j].isdigit():
j += 1
tokens.append(('-' if negative else '') + expr[i:j])
i = j
expect_operand = False
elif ch in '()':
if ch == '(':
if not expect_operand:
return None # 左括号只能出现在操作数位，如 5( 这种要拒
depth += 1
else:
if expect_operand or depth == 0:
return None # 空括号 ()，或没有配对的右括号
depth -= 1
tokens.append(ch)
expect_operand = ch == '(' # 左括号后要操作数，右括号后要运算符
i += 1
elif not expect_operand and ch in LEV:
tokens.append(ch)
expect_operand = True
i += 1
else:
return None # 运算符出现在操作数位（如 +* 连排），或非法字符
if expect_operand or depth:
return None # 空表达式 / 以运算符结尾 / 左括号没闭合
return tokens
def to_postfix(tokens: list[str]) -> list[str]:
"""调度场算法：运算符按优先级弹栈，把中缀记号改写成后缀序列。"""
out: list[str] = []
ops: list[str] = []
for tok in tokens:
if tok in LEV:
# 栈顶优先级不低于当前运算符的先算，保证同级从左到右结合
while ops and ops[-1] != '(' and LEV[ops[-1]] >= LEV[tok]:
out.append(ops.pop())
ops.append(tok)
elif tok == '(':
ops.append(tok)
elif tok == ')':
while ops[-1] != '(':
out.append(ops.pop())
ops.pop() # 丢掉左括号
else:
out.append(tok) # 操作数直接进输出
while ops:
out.append(ops.pop())
return out
def eval_postfix(postfix: list[str]) -> int | None:
"""用操作数栈求后缀表达式的值；除数为 0 视为非法，返回 None。"""
stack: list[int] = []
for tok in postfix:
if tok in LEV:
rhs, lhs = stack.pop(), stack.pop()
if tok == '/':
if rhs == 0:
return None
stack.append(divide(lhs, rhs))
else:
stack.append(APPLY[tok](lhs, rhs))
else:
stack.append(int(tok))
return stack.pop()
def solve() -> None:
# '@' 是结束符；题面样例里省略了它，取第一个 '@' 之前的部分即可兼容两种写法
data = iter(sys.stdin.buffer.read().split(b'@'))
expr = next(data).decode().strip()
tokens = tokenize(expr)
if tokens is None:
print('NO')
return
value = eval_postfix(to_postfix(tokens))
print('NO' if value is None else value)
if __name__ == "__main__":
solve()C++ 版（同一算法）：
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-05 11:53
* update_at: 2026-10-05 11:53
*/
// main.cpp：中缀表达式求值。先切词校验合法性，再用调度场算法转成后缀，
// 最后用操作数栈从左到右归约求值；任一阶段失败就输出 NO。
#include <cstdio>
#include <cstring>
typedef long long ll;
const int MAXN = 512; // 表达式长度很小，512 足够容纳整行
char raw[MAXN]; // 读入的原始内容（可能带首尾空白）
char expr[MAXN]; // 去掉首尾空白、截到 '@' 之前的表达式
int len; // expr 的字符个数
// 记号数组：kind 为 0 表示运算数（值在 tok_num），为 1 表示运算符或括号（字符在 tok_op）
int tok_kind[MAXN];
ll tok_num[MAXN];
char tok_op[MAXN];
int tok_cnt;
// 后缀序列，含义同记号数组
int post_kind[MAXN];
ll post_num[MAXN];
char post_op[MAXN];
int post_cnt;
char op_stack[MAXN]; // 调度场算法：暂存还没到计算时机的中缀运算符
int op_top;
ll num_stack[MAXN]; // 求值用的操作数栈
int num_top;
int is_digit(char ch) { return '0' <= ch && ch <= '9'; }
int is_space(char ch) { return ch == ' ' || ch == '\t' || ch == '\n' || ch == '\r'; }
// 二元运算符的优先级：乘除高于加减。
int level(char op) {
if (op == '*' || op == '/') return 2;
return 1;
}
void add_number(ll value) {
tok_kind[tok_cnt] = 0;
tok_num[tok_cnt] = value;
tok_cnt++;
}
void add_op(char op) {
tok_kind[tok_cnt] = 1;
tok_op[tok_cnt] = op;
tok_cnt++;
}
// 读入整行：'@' 是结束符，取它之前的部分作为表达式。
void read_input() {
int ch;
int n = 0;
while ((ch = getchar()) != EOF && ch != '@' && n < MAXN - 1) {
raw[n] = (char)ch;
n++;
}
raw[n] = '\0';
// 去掉首尾空白，内部空白留给 tokenize 判非法
int left = 0;
int right = n - 1;
while (left <= right && is_space(raw[left])) left++;
while (right >= left && is_space(raw[right])) right--;
int k = 0;
for (int i = left; i <= right; i++) {
expr[k] = raw[i];
k++;
}
expr[k] = '\0';
}
// 切词并校验合法性：运算数位只接受数字、'(' 和一元负号，运算符位只接受
// 二元运算符和 ')'。合法返回 1，非法返回 0。
int tokenize() {
tok_cnt = 0;
len = strlen(expr);
int expect_operand = 1; // 下一个记号是否应当出现在运算数位置
int depth = 0; // 还没闭合的左括号个数
int i = 0;
while (i < len) {
char ch = expr[i];
if (is_digit(ch)) {
if (!expect_operand) return 0; // 数字只能出现在运算数位置，如 (5)3
ll value = 0;
while (i < len && is_digit(expr[i])) {
value = value * 10 + (expr[i] - '0');
i++;
}
add_number(value);
expect_operand = 0;
} else if (ch == '-' && expect_operand) {
// 运算数位置上的 '-' 是一元负号，后面必须紧跟数字
i++;
if (i >= len || !is_digit(expr[i])) return 0;
ll value = 0;
while (i < len && is_digit(expr[i])) {
value = value * 10 + (expr[i] - '0');
i++;
}
add_number(-value);
expect_operand = 0;
} else if (ch == '(') {
if (!expect_operand) return 0; // 5( 这种缺少运算符
add_op('(');
depth++;
expect_operand = 1;
i++;
} else if (ch == ')') {
if (expect_operand || depth == 0) return 0; // 空括号或多余的右括号
add_op(')');
depth--;
expect_operand = 0;
i++;
} else if (ch == '+' || ch == '-' || ch == '*' || ch == '/') {
if (expect_operand) return 0; // 运算符出现在运算数位置，如 +*
add_op(ch);
expect_operand = 1;
i++;
} else {
return 0; // 其它字符（含内部空白）一律非法
}
}
if (expect_operand || depth != 0) return 0; // 空串、以运算符结尾、括号没配对
return 1;
}
// 调度场算法：按优先级把中缀记号重排成后缀序列。
void to_postfix() {
post_cnt = 0;
op_top = 0;
for (int i = 0; i < tok_cnt; i++) {
if (tok_kind[i] == 0) {
post_kind[post_cnt] = 0;
post_num[post_cnt] = tok_num[i];
post_cnt++;
} else if (tok_op[i] == '(') {
op_stack[op_top] = '(';
op_top++;
} else if (tok_op[i] == ')') {
while (op_stack[op_top - 1] != '(') {
post_kind[post_cnt] = 1;
post_op[post_cnt] = op_stack[op_top - 1];
post_cnt++;
op_top--;
}
op_top--; // 弹出并丢掉左括号
} else {
// 栈顶优先级不低于当前运算符的先出栈，保证同级从左到右结合
while (op_top > 0 && op_stack[op_top - 1] != '(' &&
level(op_stack[op_top - 1]) >= level(tok_op[i])) {
post_kind[post_cnt] = 1;
post_op[post_cnt] = op_stack[op_top - 1];
post_cnt++;
op_top--;
}
op_stack[op_top] = tok_op[i];
op_top++;
}
}
while (op_top > 0) {
post_kind[post_cnt] = 1;
post_op[post_cnt] = op_stack[op_top - 1];
post_cnt++;
op_top--;
}
}
// 用操作数栈求后缀表达式的值；除以 0 视为非法，返回 0 表示失败。
int eval_postfix(ll &answer) {
num_top = 0;
for (int i = 0; i < post_cnt; i++) {
if (post_kind[i] == 0) {
num_stack[num_top] = post_num[i];
num_top++;
} else {
ll right = num_stack[num_top - 1]; // 后入栈的是右操作数
num_top--;
ll left = num_stack[num_top - 1];
num_top--;
char op = post_op[i];
ll value;
if (op == '+') {
value = left + right;
} else if (op == '-') {
value = left - right;
} else if (op == '*') {
value = left * right;
} else {
if (right == 0) return 0;
value = left / right; // C++ 整数除法向零取整
}
num_stack[num_top] = value;
num_top++;
}
}
answer = num_stack[0];
return 1;
}
int main() {
read_input();
if (!tokenize()) {
printf("NO\n");
return 0;
}
to_postfix();
ll answer = 0;
if (!eval_postfix(answer)) {
printf("NO\n");
return 0;
}
printf("%lld\n", answer);
return 0;
}