doju   3년 전

역사적으로 수식을 계산하는 문제는 반드시 이 과정을 겪는 것 같습니다.


문제

당신은 사칙연산을 할 줄 아는가?
식이 주어지면, 그 식을 계산하여서 사칙연산을 할 줄 안다는 것을 보여라.

이 문제에서 계산할 식은 다음의 문법으로 정의되는 <expr>이다.

<digit> = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
<number> = <digit> | <number> <digit>
<expr> = <number> | <expr> '+' <expr> | <expr> '-' <expr> | <expr> '*' <expr> | <expr> '/' <expr> | '(' <expr> ')'

입력

첫째 줄에 계산해야 하는 식이 주어진다. 식은 ()*/+-0123456789의 문자로만 이루어져 있으며, 길이는 1,000자 이하이다.

출력

식의 계산 결과를 출력한다. 만약 식이 올바르지 않아 계산할 수 없는 경우라면 ROCK을 출력한다.

  • 식을 계산할 때는 일반적인 연산의 우선순위를 따른다. 즉 괄호(()) 안의 식 → 곱하기(*)와 나누기(/) → 더하기(+)와 빼기(-) 순서대로 계산하며, 같은 순위의 연산이 여러 개일 경우 왼쪽부터 순서대로 계산한다.
  • 주어진 식이 위의 문법을 만족할 경우, 식을 계산하는 과정에서 나눗셈이 등장한다면 반드시 나눗셈의 결과가 정수로 나누어떨어지거나 제수(나누는 수)가 0임이 보장된다. 이때, 제수가 0인 경우가 등장한다면 식이 올바르지 않은 것으로 간주한다.

예제 입력 1

5+(1+2)*3

예제 출력 1

14

예제 입력 2

(+6+3)

예제 출력 2

ROCK

위 문법은 불필요한 leading zero를 허용합니다. 이를 허용하지 않고자 할 경우, 문법을 아래와 같이 바꿔야 합니다.

<non-zero> = '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
<digit> = '0' | <non-zero>
<digits> = '' | <digit> <digits>
<number> = '0' | <non-zero> <digits>
<expr> = <number> | <expr> '+' <expr> | <expr> '-' <expr> | <expr> '*' <expr> | <expr> '/' <expr> | '(' <expr> ')'

startlink   3년 전

수정했습니다.

powergee   3년 전

문제 설명과 데이터가 상당히 애매했던 문제였는데, 솔선수범해주셔서 감사합니다. 업데이트된 지문에 의견이 있어서 댓글을 남깁니다.

1. "출력" 문단에 bullet list 로 나열된 규칙들을 "문제" 문단으로 옮기는 것은 어떨까요? 적힌 규칙들이 출력에 대한 규칙이라기보다 실제 알고리즘을 구현하는데 꼭 필요한 규칙들이라서 "문제" 문단에서 BNF 아래에 함께 제시하는 것이 자연스러울 것 같습니다.

2. BNF에는 연산자 간 우선순위(곱셈과 나눗셈이 덧셈과 뺄셈보다 우선)를 반영되어 있지 않고 대신 이를 글로 설명하고 있는데, "term"/"factor" 같은 논터미널을 추가해서 우선순위도 고려되도록 나타내는 것은 어떨까요? 예를 들어 아래처럼 작성할 수 있을 것 같습니다.

<digit> = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
<number> = <digit> | <number> <digit>
<factor> = <number> | '(' <expr> ')'
<term> = <factor> | <factor> '*' <term> | <factor> '/' <term>
<expr> = <term> | <term> '+' <expr> | <term> '-' <expr>

(그런데 이 안은 장단점이 있는것 같은것이, BNF를 이렇게 수정하면 문법 정의는 더 엄밀해지지만 너무 많은 구현 디테일을 스포하는 것 같기도 하네요...)

이것들을 반영하면 결과 지문은 아래와 같습니다. 누구나 의견 주시면 감사드리겠습니다.


문제

당신은 사칙연산을 할 줄 아는가?
식이 주어지면, 그 식을 계산하여서 사칙연산을 할 줄 안다는 것을 보여라.

이 문제에서 계산할 식은 다음의 문법으로 정의되는 <expr>이다.

<digit> = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
<number> = <digit> | <number> <digit>
<factor> = <number> | '(' <expr> ')'
<term> = <factor> | <factor> '*' <term> | <factor> '/' <term>
<expr> = <term> | <term> '+' <expr> | <term> '-' <expr>

식을 계산할 때는 아래와 같은 규칙을 따른다.

  • 식을 계산할 때 같은 순위의 연산이 여러 개일 경우, 왼쪽부터 순서대로 계산한다. 예를 들어 6*2/3와 같은 식이 주어지면 왼쪽부터 계산하여 결과는 4가 된다.
  • 주어진 식이 위의 문법을 만족할 경우, 식을 계산하는 과정에서 나눗셈이 등장한다면 반드시 나눗셈의 결과가 정수로 나누어떨어지거나 제수(나누는 수)가 0임이 보장된다. 이때, 제수가 0인 경우가 등장한다면 식이 올바르지 않은 것으로 간주한다.

입력

첫째 줄에 계산해야 하는 식이 주어진다. 식은 ()*/+-0123456789의 문자로만 이루어져 있으며, 길이는 1,000자 이하이다.

출력

식의 계산 결과를 출력한다. 만약 식이 올바르지 않아 계산할 수 없는 경우라면 ROCK을 출력한다.

예제 입력 1

5+(1+2)*3

예제 출력 1

14

예제 입력 2

(+6+3)

예제 출력 2

ROCK

doju   3년 전

1. 좋아 보입니다.

2. 문법은 식을 어떻게 계산해야 하는지를 내포하지 않습니다. 식을 문법에 따라 해석한 결과가 주어진 우선순위를 따르도록 하기 위해서 non-terminal을 넣는 것이지, "non-terminal을 두면 우선순위는 없어도 된다"는 앞뒤가 뒤바뀐 주장입니다.

댓글을 작성하려면 로그인해야 합니다.