Snowflake 面试题：实现一个迷你编程语言解释器（SnowCal Interpreter）

# Snowflake 面试题：实现一个迷你编程语言解释器（SnowCal Interpreter）

题目描述

SnowCal is a simple programming language used to perform calculations. A SnowCal program keeps a single integer X in memory, initially set to zero, and repeatedly performs addition and multiplication operations on it.

Formally, the language has 5 operations:

ADD Y → add Y to X
MUL Y → multiply X by Y
FUN F → begin the definition of a function with unique name F
END → end of current function
INV F → invoke function F

Write an interpreter that takes in the commands as an array of strings and returns the final value of X.

示例

Example 1

Input:

MUL 2
ADD 3

Output:

解释：X 初始为 0，先 X *= 2 得 0，再 X += 3 得 3

Example 2

Input:

FUN INCREMENT
ADD 1
END
INV INCREMENT
MUL 2
ADD 3

Output:

解释：

定义函数 INCREMENT：ADD 1
调用 INCREMENT：X = 0 + 1 = 1
MUL 2：X = 1 × 2 = 2
ADD 3：X = 2 + 3 = 5

问题分析

这道题要求你实现一个简单编程语言 SnowCal 的解释器。语言中只有一个整数变量 X（初始为 0），支持五种指令：

ADD Y → X += Y
MUL Y → X *= Y
FUN F → 开始定义名为 F 的函数
END → 函数定义结束
INV F → 调用函数 F

你需要按顺序解析指令、保存函数定义，并在执行过程中正确处理函数调用（包括嵌套和多次调用）。最终返回执行完所有命令之后 X 的值。

这道面试题重点考察：

解释器设计能力
函数定义与作用域管理
指令解析（parsing）
状态管理与执行引擎实现

属于中高级工程师常见的系统设计类 Coding 题。

解法实现

class SnowCalInterpreter:
    def __init__(self):
        self.X = 0
        self.functions = {}  # 存储函数定义
    
    def interpret(self, commands):
        """
        解释执行 SnowCal 命令
        
        Args:
            commands: 命令列表，例如 ['ADD', '5', 'MUL', '2']
        
        Returns:
            最终 X 的值
        """
        i = 0
        while i < len(commands):
            cmd = commands[i]
            
            if cmd == 'ADD':
                value = int(commands[i + 1])
                self.X += value
                i += 2
            
            elif cmd == 'MUL':
                value = int(commands[i + 1])
                self.X *= value
                i += 2
            
            elif cmd == 'FUN':
                func_name = commands[i + 1]
                i += 2
                
                # 找到函数体（直到 END）
                func_body = []
                depth = 1  # 处理嵌套函数定义
                
                while depth > 0:
                    if commands[i] == 'FUN':
                        depth += 1
                    elif commands[i] == 'END':
                        depth -= 1
                        if depth == 0:
                            break
                    func_body.append(commands[i])
                    i += 1
                
                self.functions[func_name] = func_body
                i += 1  # 跳过 END
            
            elif cmd == 'INV':
                func_name = commands[i + 1]
                if func_name in self.functions:
                    # 递归执行函数体
                    self.interpret(self.functions[func_name])
                i += 2
            
            else:
                i += 1
        
        return self.X


def snowcal_interpreter(commands):
    """
    简化版接口
    """
    interpreter = SnowCalInterpreter()
    return interpreter.interpret(commands)

测试用例

# Test 1: 基础运算
commands1 = ['MUL', '2', 'ADD', '3']
print(snowcal_interpreter(commands1))  # 输出: 3

# Test 2: 函数调用
commands2 = [
    'FUN', 'INCREMENT',
    'ADD', '1',
    'END',
    'INV', 'INCREMENT',
    'MUL', '2',
    'ADD', '3'
]
print(snowcal_interpreter(commands2))  # 输出: 5

# Test 3: 多次函数调用
commands3 = [
    'FUN', 'DOUBLE',
    'MUL', '2',
    'END',
    'ADD', '5',
    'INV', 'DOUBLE',
    'INV', 'DOUBLE'
]
print(snowcal_interpreter(commands3))  # 输出: 20 (5 * 2 * 2)

# Test 4: 嵌套函数定义
commands4 = [
    'FUN', 'OUTER',
    'FUN', 'INNER',
    'ADD', '1',
    'END',
    'INV', 'INNER',
    'MUL', '2',
    'END',
    'INV', 'OUTER'
]
print(snowcal_interpreter(commands4))  # 输出: 2

优化版本：支持参数和返回值

class AdvancedSnowCalInterpreter:
    def __init__(self):
        self.X = 0
        self.functions = {}
        self.call_stack = []  # 调用栈
    
    def interpret(self, commands):
        i = 0
        while i < len(commands):
            cmd = commands[i]
            
            if cmd == 'ADD':
                value = int(commands[i + 1])
                self.X += value
                i += 2
            
            elif cmd == 'MUL':
                value = int(commands[i + 1])
                self.X *= value
                i += 2
            
            elif cmd == 'FUN':
                func_name = commands[i + 1]
                i += 2
                func_body = []
                depth = 1
                
                while depth > 0:
                    if commands[i] == 'FUN':
                        depth += 1
                    elif commands[i] == 'END':
                        depth -= 1
                        if depth == 0:
                            break
                    func_body.append(commands[i])
                    i += 1
                
                self.functions[func_name] = func_body
                i += 1
            
            elif cmd == 'INV':
                func_name = commands[i + 1]
                if func_name in self.functions:
                    # 保存当前状态
                    self.call_stack.append(self.X)
                    self.interpret(self.functions[func_name])
                i += 2
            
            elif cmd == 'RET':
                # 返回到调用点
                if self.call_stack:
                    self.call_stack.pop()
                i += 1
            
            else:
                i += 1
        
        return self.X

扩展功能

1. 支持变量

class SnowCalWithVariables:
    def __init__(self):
        self.variables = {'X': 0}
        self.functions = {}
    
    def interpret(self, commands):
        i = 0
        while i < len(commands):
            cmd = commands[i]
            
            if cmd == 'SET':
                var_name = commands[i + 1]
                value = int(commands[i + 2])
                self.variables[var_name] = value
                i += 3
            
            elif cmd == 'GET':
                var_name = commands[i + 1]
                return self.variables.get(var_name, 0)
            
            # ... 其他指令

2. 支持条件语句

# 新增指令
# IF X > Y THEN ... END
# WHILE X < Y DO ... END

3. 支持递归

# 斐波那契数列
commands = [
    'FUN', 'FIB',
    'IF', 'X', '<=', '1',
    'RET', 'X',
    'ELSE',
    'ADD', 'X', '-1',
    'INV', 'FIB',
    'ADD', 'X', '-2',
    'INV', 'FIB',
    'END'
]

常见错误

未处理嵌套函数定义：需要用 depth 计数器
函数调用时状态污染：需要保存和恢复 X 的值
无限递归：需要检测递归深度
指令解析错误：索引越界、类型转换失败

总结

SnowCal 解释器题考察点：

指令解析：字符串处理和状态机
函数管理：定义、存储、调用
嵌套处理：深度计数和栈管理
状态维护：变量和调用栈

oavoservice 专注于 Snowflake / Google / Amazon 等大厂面试辅导，提供 OA 代做、VO 实时辅助等服务。如需帮助，欢迎联系我们。

需要面试真题？立刻联系微信 Coding0201，获得真题。