如何按指定长度生成仅含1、指定运算符及括号的所有合法表达式？

假设存在若干一元运算符（取反、按位取反等）、若干二元运算符（加、减、乘、除、移位等），唯一允许的操作数为数字1，且允许使用括号分组。是否存在方法可生成指定长度的所有合法（且仅合法）表达式？

示例展示 #

4字符合法表达式子集 #

(-1)
-1*1
~(1)
~-~1
// 更多示例...

7字符合法表达式示例 #

(1+1)<<1 // 假设移位运算符算1个字符，代表1种操作
1/(1>>1) // 无法求值的表达式（如1/0）也被允许，只要能被解析即可
-~(1-1)
// 更多示例...

复杂分组的长表达式示例 #

((1<<(1+1+1))*(1+1))/((1<<(1+1))+1)

结论：存在可行方法 #

核心是基于**递归+上下文无关文法（CFG）**的生成策略，结合长度约束和合法性校验，就能精准生成指定长度的所有合法表达式。

具体实现思路 #

1. 定义文法规则
   先明确合法表达式的构成规则（简化版）：

• 基础表达式：1（长度1）
• 一元运算表达式：[一元运算符] + [合法表达式]，或([合法表达式])
• 二元运算表达式：[合法表达式] + [二元运算符] + [合法表达式]，或([合法表达式] + [二元运算符] + [合法表达式])

2. 带长度约束的递归生成
   每一步生成时追踪当前字符串的长度：

• 若当前长度等于目标长度，检查是否为合法表达式（比如括号是否平衡、运算符位置是否合规），符合则保留。
• 若当前长度小于目标长度，根据文法规则继续扩展（比如在当前表达式后加二元运算符+1，或在开头加一元运算符等）。
• 若当前长度超过目标长度，直接剪枝终止递归。

3. 合法性与去重处理

• 括号平衡：维护计数器，左括号+1，右括号-1，确保全程计数器非负，最终为0。
• 运算符合法性：一元运算符只能出现在表达式开头、左括号之后或其他运算符之后；二元运算符必须夹在两个合法表达式中间。
• 去重：通过字符串哈希记录已生成的表达式，避免重复产出。

内容的提问来源于stack exchange，提问作者Steven