한 단계씩 수식 풀기

초등학교 대수 교재를 쓰는 저자가, 풀이 해설집을 만들 때 사람의 실수를 없애기 위해 간단한 대수 방정식을 한 단계씩 풀어 주는 프로그램을 부탁했습니다.

모든 문제는 정수 상수, 네 가지 사칙연산자(+, -, *, /), 등호, 그리고 변수 하나로 이루어진 대수적 등식입니다. 예를 들어 12 - 4 * 3 = x 와 같은 형태입니다.

방정식은 단순히 답만 구하는 것이 아니라, 표준 연산자 우선순위에 따라 한 번에 한 연산씩 줄여 나가야 합니다. 먼저 모든 곱셈과 나눗셈을 왼쪽에서 오른쪽 순서로 계산하고, 그다음 모든 덧셈과 뺄셈을 왼쪽에서 오른쪽 순서로 계산합니다. 매 단계에서는 현재 남아 있는 연산 중 우선순위가 가장 높으면서 가장 왼쪽에 있는 연산 하나만 수행하고, 그 결과로 얻은 식을 한 줄에 출력합니다. 모든 나눗셈은 항상 나누어떨어져 정수 결과를 낸다고 가정해도 됩니다.

입력은 여러 개의 방정식으로 이루어지며, 각 방정식은 한 줄에 하나씩 주어지고 파일의 끝에서 입력이 끝납니다.

각 방정식은 1개 이상 20개 이하의 연산과, 따라서 2개 이상 21개 이하의 정수 피연산자를 가집니다(피연산자의 개수는 항상 연산자의 개수보다 정확히 하나 많습니다). 각 피연산자는 앞에 단항 부호(+ 또는 -)가 붙을 수 있습니다. 연산자와 피연산자 사이의 공백은 있어도 되고 전혀 없어도 됩니다. 우변의 변수 이름은 1자 이상 8자 이하의 알파벳 문자로 이루어집니다.

각 방정식에 대해 먼저 그 방정식 자체를 출력하고, 이후 한 번의 연산을 수행할 때마다 결과 식을 한 줄씩 출력합니다. 좌변에 값이 하나만 남을 때까지 반복합니다.

각 줄은 모든 피연산자, 연산자, 그리고 = 기호 사이에 공백을 정확히 하나씩 두어 출력합니다(예: 2 * -3 + -6 - 4 = r). 음수 피연산자는 앞에 - 를 붙여 출력하고, 음수가 아닌 피연산자는 부호 없이 출력합니다(입력에 있던 단항 + 는 제거됩니다). 서로 다른 방정식의 출력 사이에는 빈 줄을 하나씩 넣어 구분합니다.