계산기 만들기

규칙을 코드로 옮깁니다

"1 + 2 * 3" 은 글자입니다. 여기서 7을 얻으려면 두 가지를 해야 합니다. 글자를 숫자와 기호로 나누고, 곱하기를 먼저 한다는 규칙을 지켜야 합니다.

if 로 하려 들면 곧 막힙니다. 곱하기를 먼저 찾아 셈하고 돌아오는 식으로 적을 수는 있는데, 괄호가 나오면 그 안을 먼저 해야 하고 그 안에 또 괄호가 있을 수 있습니다.

그래서 규칙을 문장으로 적는 것부터 합니다. 셋이면 됩니다.

식  = 항 (('+' | '-') 항)*
항  = 인자 (('*' | '/') 인자)*
인자 = 숫자 | '(' 식 ')' | '-' 인자

이 셋이 그대로 메서드 셋이 됩니다. 우선순위는 따로 처리하지 않습니다. 식 이 항 을 부르고 항 이 인자 를 부르는 순서 자체가 곱하기를 먼저 하게 만듭니다.

괄호도 저절로 풀립니다. 인자 가 다시 식 을 부르기 때문입니다. 이것을 재귀 하강이라고 합니다.

돌아가는 계산기

아래 코드는 브라우저 안에서 실제로 실행됩니다. 고쳐서 눌러 보셔도 됩니다.

using System.Globalization;

string[] tests = [
    "1 + 2 * 3", "(1 + 2) * 3", "10 / 4", "-3 + 5",
    "2 * (3 + 4) - 10 / 5", "10 - 3 - 2", "0.1 + 0.2",
    "1 / 0", "1 + ", "(1 + 2", "1 & 2",
];

foreach (var t in tests) {
    try { Console.WriteLine($"{t,-22} = {Calculator.Eval(t)}"); }
    catch (Exception ex) when (ex is FormatException or DivideByZeroException) {
        Console.WriteLine($"{t,-22} ! {ex.Message}");
    }
}

static class Calculator {
    public static decimal Eval(string text) {
        var p = new Parser(text);
        var value = p.Expression();
        p.ExpectEnd();
        return value;
    }
}

// 식을 왼쪽부터 한 글자씩 지나가며 셈합니다.
ref struct Parser(ReadOnlySpan<char> text) {
    private readonly ReadOnlySpan<char> _text = text;
    private int _i = 0;

    // 식 = 항 (('+' | '-') 항)*
    public decimal Expression() {
        var left = Term();

        while (true) {
            if (Take('+')) left += Term();
            else if (Take('-')) left -= Term();
            else return left;
        }
    }

    // 항 = 인자 (('*' | '/') 인자)*
    private decimal Term() {
        var left = Factor();

        while (true) {
            if (Take('*')) left *= Factor();
            else if (Take('/')) {
                var right = Factor();
                if (right == 0) throw new DivideByZeroException("0 으로 나눌 수 없습니다.");
                left /= right;
            }
            else return left;
        }
    }

    // 인자 = 숫자 | '(' 식 ')' | '-' 인자
    private decimal Factor() {
        if (Take('-')) return -Factor();

        if (Take('(')) {
            var inner = Expression();
            if (!Take(')')) throw new FormatException("닫는 괄호가 없습니다.");
            return inner;
        }

        return Number();
    }

    private decimal Number() {
        Skip();
        var start = _i;
        while (_i < _text.Length && (char.IsDigit(_text[_i]) || _text[_i] == '.')) _i++;

        if (start == _i)
            throw new FormatException($"숫자가 와야 할 자리입니다({_i + 1}번째 글자).");

        return decimal.Parse(_text[start.._i], CultureInfo.InvariantCulture);
    }

    // 다음 글자가 c 면 지나가고 true 를 돌려줍니다.
    private bool Take(char c) {
        Skip();
        if (_i >= _text.Length || _text[_i] != c) return false;
        _i++;
        return true;
    }

    private void Skip() { while (_i < _text.Length && _text[_i] == ' ') _i++; }

    public void ExpectEnd() {
        Skip();
        if (_i < _text.Length)
            throw new FormatException($"읽을 수 없는 글자입니다('{_text[_i]}').");
    }
}

코드는 고쳐서 실행해 볼 수 있습니다. 처음 누를 때만 실행기를 내려받느라 잠시 걸립니다. 적은 코드는 서버로 나가지 않습니다.

우선순위를 다루는 코드가 한 줄도 없습니다. 그런데 곱하기가 먼저 되었고 괄호도 풀렸습니다. 어떻게 그렇게 되는지가 아래의 이야기입니다.

부르는 순서가 우선순위입니다

1 + 2 * 3 을 넣으면 이렇게 갑니다.

Expression()          1 을 얻으려고 Term() 을 부릅니다
  Term()              1 을 얻으려고 Factor() 를 부릅니다
    Factor()  → 1
  Term()              다음이 '*' 이므로 Factor() 를 또 부릅니다… 가 아닙니다
                      다음은 '+' 라 Term() 은 1 만 돌려주고 끝납니다
Expression()          '+' 를 지나고 오른쪽 Term() 을 부릅니다
  Term()              2 를 얻고, 다음이 '*' 이므로 계속합니다
    Factor()  → 3     2 * 3 = 6 을 돌려줍니다
Expression()          1 + 6 = 7

Term 이 곱하기를 다 끝내고 나서야 Expression 으로 돌아갑니다. 곱하기가 더 아래에 있으므로 먼저 끝나는 것이고, 그것이 우선순위입니다.

우선순위를 하나 더 넣고 싶으면 단계를 하나 더 만들면 됩니다. 거듭제곱을 곱하기보다 먼저 하게 하려면 Factor 아래에 한 단계를 둡니다.

괄호는 되돌아가는 것뿐

Factor 가 여는 괄호를 만나면 Expression 을 처음부터 다시 부릅니다.

if (Take('(')) {
    var inner = Expression();
    if (!Take(')')) throw new FormatException("닫는 괄호가 없습니다.");
    return inner;
}

몇 겹이든 상관없습니다. 안쪽 괄호가 다시 Factor 를 거쳐 Expression 을 부르기 때문입니다. 겹치는 깊이를 세는 코드가 필요 없습니다.

닫는 괄호를 여기서 확인하는 것이 중요합니다. 열었으면 그 자리에서 닫히는지 보아야, (1 + 2 가 조용히 3으로 셈되지 않습니다.

빼기는 왼쪽부터

10 - 3 - 2 는 5입니다. 9가 아닙니다. while 로 왼쪽부터 접어 나가기 때문입니다.

var left = Term();          // 10

while (true) {
    if (Take('-')) left -= Term();   // 10 - 3 = 7,  그다음 7 - 2 = 5
    …
}

재귀로 적으면 틀립니다. 오른쪽을 Expression() 으로 부르면 10 - (3 - 2) 가 되어 9가 나옵니다. 더하기와 곱하기는 결과가 같아 넘어가지만, 빼기와 나누기에서 드러납니다.

while (Take('-'))
    left -= Term();

// (10 - 3) - 2 = 5

if (Take('-'))
    return left - Expression();

// 10 - (3 - 2) = 9   틀립니다

돈을 다룬다면 decimal

5.1에서 금액에 double 을 사용하지 말라고 했습니다. 계산기에서 그것이 그대로 보입니다.

Console.WriteLine(0.1 + 0.2);          // 0.30000000000000004
Console.WriteLine(0.1 + 0.2 == 0.3);    // False

Console.WriteLine(0.1m + 0.2m);        // 0.3
Console.WriteLine(0.1m + 0.2m == 0.3m);  // True

double 은 2진 소수라 0.1을 정확히 담지 못합니다. 화면에 0.3으로 보여도 값은 조금 다르고, 비교하면 어긋납니다. 사람이 10진으로 적은 것을 다룬다면 decimal 입니다.

대신 느립니다. 물리 계산이나 그래픽처럼 자릿수보다 속도가 중요한 자리에서는 double 이 맞습니다.

어디서 틀렸는지 말해 주기

"잘못된 식입니다" 만으로는 고칠 수 없습니다. 무엇이 왜 안 되는지를 셋으로 나누어 적었습니다.

ExpectEnd 가 없으면 어떻게 되는지 보십시오. "1 & 2" 에서 Expression 은 1까지만 읽고 만족해서 돌아갑니다. 뒤에 무엇이 남았는지 아무도 보지 않으면 조용히 1이 답으로 나갑니다.

public static decimal Eval(string text) {
    var p = new Parser(text);
    var value = p.Expression();
    p.ExpectEnd();          // 이 줄이 없으면 "1 & 2" 가 1 이 됩니다
    return value;
}

다 읽었는지 확인하는 것이 파싱의 마지막 단계입니다. 빠뜨리기 쉽고, 빠뜨리면 틀린 답이 오류 없이 나갑니다.

ref struct 인 까닭

Parser 가 ReadOnlySpan<char> 를 담으므로 ref struct 여야 합니다(4.8). 식을 자를 때마다 새 문자열이 생기지 않습니다.

ref struct Parser(ReadOnlySpan<char> text) {
    private readonly ReadOnlySpan<char> _text = text;
    private int _i = 0;

여기서는 string 으로 두어도 됩니다. 식 하나는 짧고 사람이 한 번 누를 때마다 한 번 도는 자리라, 만드는 것을 아껴 봐야 값이 없습니다. 4.8에서 본 대로 먼저 재고 나서 고칠 자리입니다.

그래도 이렇게 적은 것은 이 모양이 자연스럽기 때문입니다. 자리를 하나씩 지나가며 읽는 코드는 잘라 담을 일이 없고, 그럴 때 Span 이 오히려 읽기 좋습니다.

직접 해보기