문제
Evaluate a small stack language. The stack starts empty; integers push values onto its top. Return the final stack from bottom to top. Tokens are separated by spaces and command names are case-insensitive.
Arithmetic +, -, *, / pops the top value as right operand and the next as left operand, then pushes left operator right. Division truncates toward zero. DUP copies the top value; DROP removes it; SWAP exchanges the top two; OVER copies the second-from-top value onto the top.
Define a word with : name body ;. A name contains only letters. The nonempty body may contain integers, built-in commands, and previously defined words. Definitions do not execute their bodies. Redefining a name affects later uses, but older definitions keep the meanings captured when they were defined. A definition may use the previous version of its own name. Nested definitions, forward references, and recursive calls are not allowed.
Every test program is valid: no unknown word, stack underflow, division by zero, or overflow occurs. You do not need to report errors.
Implement mini_stack_language_interpreter(program).
Input
program: The complete valid program.
Output
Return the final stack in bottom-to-top order.
제약 조건
0…10,000 tokens. At most 100,000 primitive tokens across all expanded definitions and executed code. Values and intermediate arithmetic fit signed 64-bit. Integer literals use optional minus followed by digits. Tokens : and ; are separate. Built-in names cannot be redefined; user words can be redefined. Empty input returns an empty stack.
예시
입력:
program = ": square dup * ; 5 square 3 +"
예상 출력:
expected = [28]입력:
std::string program = ": square dup * ; 5 square 3 +";
예상 출력:
std::vector<long long> expected = {28};입력:
string program = ": square dup * ; 5 square 3 +";
예상 출력:
long[] expected = new long[] {28};설명
Define square without executing it. Push 5, duplicate it, multiply to get 25, then push 3 and add to obtain 28.
입력:
program = "-7 2 / 9 over"
예상 출력:
expected = [-3, 9, -3]입력:
std::string program = "-7 2 / 9 over";
예상 출력:
std::vector<long long> expected = {-3, 9, -3};입력:
string program = "-7 2 / 9 over";
예상 출력:
long[] expected = new long[] {-3, 9, -3};설명
−7 divided by 2 truncates toward zero to −3. Push 9, then OVER copies the second-from-top value, −3.
접근 방법
먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.
힌트 1
프로그램을 현재 스택을 실행하는 일과, 각 단어가 정의될 당시 무엇을 뜻했는지 기억하는 일로 나눠서 보세요.
힌트 2
사용자 정의 단어는 해석된 연산들의 시퀀스로 저장해 두면, 나중에 다시 정의돼도 이전 본문은 바뀌지 않습니다.
힌트 3
정의 시 파싱을 조심하세요: 현재 의미로 단어를 캡처하고, 정의 안에서는 실행을 무시하며, 대소문자 구분 없는 내장 명령과 0으로 버리는 나눗셈을 처리해야 합니다.
예상 복잡도
시간 O(T), 추가 공간 O(T)
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.