맥주 청구서

술집 청구서는 컴퓨터가 존재하기 훨씬 전부터 일상에 들어와 있었다. 사람들은 청구서를 한 번 지불하고 나면 더 이상 주목할 가치가 없는 불쌍한 종이 조각이라고 생각하는 경향이 있다. 그러나 기존 컴퓨터과학의 흐름이 완전히 간과한 사실은, 청구서에 적힌 낙서가 여러 형식 언어 응용과 분석에 적합한, 매우 형식화되어 있고 흔히 상당히 비자명한 텍스트라는 점이다.

청구서는 문자로 이루어진 줄들로 구성된다. 각 줄은 가격 줄 또는 갈퀴 줄이다. 가격 줄은 양의 정수, 즉 음식이나 음료 항목의 가격으로 시작하며, 그 뒤에 선택적으로 여러 개의 세로 막대가 붙는다. 그 줄의 가격은 다음과 같이 계산한다. 막대가 있으면 그 줄의 가격은 항목 가격에 막대의 개수를 곱한 값이다. 막대가 없으면 그 줄의 가격은 항목 가격과 같다. 갈퀴 줄은 세로 막대만 포함하며(갈퀴의 이빨과 비슷하다는 뜻에서 갈퀴 줄이라는 이름이 붙었다), 막대 하나는 청구서 소지자가 산 맥주 한 잔을 나타낸다. 갈퀴 줄의 가격은 맥주 한 잔의 가격에 그 줄의 막대 개수를 곱한 값이다. 이 문제에서 맥주 가격은 42 화폐 단위이다. 청구서 합계는 청구서의 모든 줄 가격을 더한 값이다.

우리는 이른바 갈퀴 청구서 언어(Raked bill language)의 형식적 정의를 여기 제시한다. 우리가 아는 한 컴퓨터과학의 역사 전체에서 이런 것은 처음이다. 이 문제의 청구서는 갈퀴 청구서 언어로 표현된다.

<BILL>        ::=  <LINE> | <LINE><BILL>
<LINE>        ::=  <PRICED_LINE><line_break> | <RAKE_LINE><line_break>
<PRICED_LINE> ::=  <PRICE_SPEC> | <PRICE_SPEC><RAKE>
<RAKE_LINE>   ::=  <RAKE>
<PRICE_SPEC>  ::=  <PUB_INTEGER><comma><hyphen>
<RAKE>        ::=  <rake_dent> | <rake_dent><RAKE>
<PUB_INTEGER> ::=  <dig_1_9> | <dig_1_9><DIG_SEQ>
<DIG_SEQ>     ::=  <dig_0_9> | <dig_0_9><DIG_SEQ>
<dig_1_9>     ::=  '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
<dig_0_9>     ::=  '0' | <dig_1_9>
<rake_dent>   ::=  '|' // ascii character 124
<comma>       ::=  ',' // ascii character 44
<hyphen>      ::=  '-' // ascii character 45
<line_break>  ::=  LF // ascii character 10, line feed

위 언어 명세에서 청구서에 실제로 나타나는 문자는 명세의 다른 부분과 구별하기 위해 작은따옴표로 묶었다. 기호 //는 한 줄 주석을 시작하며, 언어 정의의 일부가 아니다.

입력은 청구서를 지정하는 비어 있지 않은 줄의 나열이다. 각 입력 줄은 가격 줄 또는 갈퀴 줄이다. 가격 줄은 1 000을 넘지 않는 양의 정수로 시작하며, 바로 뒤에 쉼표와 빼기 기호가 온다. 빼기 기호 뒤에는 선택적으로 0이 아닌 개수의 세로 막대가 붙는다. 갈퀴 줄은 0이 아닌 개수의 세로 막대만 포함하고 다른 기호는 없다. 청구서 전체에서 세로 막대는 '|', 즉 아스키 문자 124로 나타낸다. 각 줄은 최대 1 000개의 문자를 포함하며, 줄에 공백은 없다. 입력 줄은 최대 1 000개이다. 입력에는 빈 줄이 없다. 모든 가격은 같은 화폐 단위로 표현된다.

청구서 합계를 10 단위로 올림한 수 하나를 출력한다. 수는 형식에 맞게, 즉 바로 뒤에 쉼표와 빼기 기호가 오도록 출력해야 한다.