035. 수식 파서

[문제] 사칙연산 수식을 다루는 MCP 서버를 구현한다. 입력 수식은 토큰(숫자, 연산자, 괄호) 사이가 공백으로 구분된 문자열이다. 예: "3 + 4 * 2". 지원하는 연산은 더하기(+), 빼기(-), 곱하기(*), 나누기(/)와 괄호 ( ) 다. 곱하기/나누기는 더하기/빼기보다 우선순위가 높다. 예를 들어 3 + 4 * 2 는 4*2 를 먼저 계산해 3 + 8 = 11 이 된다. 후위 표기법(postfix, RPN)이란 연산자를 피연산자 뒤에 쓰는 표기법이다. 중위 표기 3 + 4 * 2 는 후위 표기로 "3 4 2 * +" 가 된다(곱을 먼저 한 뒤 더한다는 뜻). [구현할 함수] - parse_expression(expression: str) -> List[str] 수식을 공백 기준으로 토큰 분리해 배열로 반환한다. 숫자, 연산자, 괄호 모두 각각 하나의 토큰이다. - evaluate(expression: str) -> float 수식을 연산자 우선순위와 괄호를 고려해 계산한 값을 실수로 반환한다. - to_postfix(expression: str) -> str 중위 표기 수식을 후위 표기 문자열로 변환해 반환한다. 토큰 사이는 공백 하나로 구분한다. [입력·상태] 별도 상태는 없다. 입력은 토큰이 공백으로 구분된 유효한 중위 표기 수식 문자열이다. [제약] - 지원 연산자: + - * / 와 괄호 ( ). - 곱하기/나누기가 더하기/빼기보다 우선순위가 높고, 괄호가 가장 우선한다. - evaluate 의 반환은 실수(float)다. [힌트] 중위 -> 후위 변환은 "스택을 이용한 연산자 우선순위 처리"(Shunting-yard 알고리즘) 개념을 사용한다. 스택 자료구조는 Python list, C++ std::stack, Java java.util.Deque 등으로 구현할 수 있다. [예시] parse_expression("3 + 4 * 2") -> ["3", "+", "4", "*", "2"] evaluate("3 + 4 * 2") -> 11.0 # 곱셈 우선 to_postfix("3 + 4 * 2") -> "3 4 2 * +"