LISP 계산기

LISP은 괄호로 유명한 언어다. 이 문제는 LISP 형태로 표현된 4칙연산 산술식을 계산하는 계산기 프로그램을 작성하는 것이다.

LISP 표현식은 여는 괄호와 공백으로 구분된 항(term)의 목록 그리고 닫는 괄호로 만들어진다. 첫 번째 항은 +, -, *, /와 같은 심볼이며 나머지 항은 1, 2, 10, -10 등의 정수 혹은 또다른 LISP 표현식이 될 수 있다. 말하자면 연산자들이 가변 길이 인자를 받는 셈이다.

더하기의 경우 (+ 1 2 3)은 6이다. (+)만 단독으로 사용된 경우는 0이다. 곱하기의 경우는 기본 값이 1이고, 빼기와 나누기는 인자가 최소 하나 이상 있어야 한다. 아래는 빼기와 곱하기의 예를 보여준다. (화살표는 결과값을 나타낸다)

(- 10 3) → 7
(- 10 3 5)  → 2
(* 2 3) → 6
(* 2 3 4) → 24

괄호가 중쳡된 경우는 아래와 같다.

(* (+ 2 3) (- 5 3)) → 10
(/ (+ 9 1) (+ 2 3)) → 2

모두 괄호로 묶여있기 때문에 +, -, *, / 연산자 사이의 우선순위는 따로 신경쓸 필요 없다.

recursive descent parser
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

6개의 풀이가 있습니다.

import re

def eval(op, variables):
    variable = list(map(int, variables.split()))
    if op == '+':
        out = sum(variable)
    elif op == '-':
        out = variable[0]
        for i in range(2,len(variable)):
            out -= variable[i]
    elif op == '*':
        out = 1
        for i in range(len(variable)):
            out *= variable[i]
    elif op == '/':
        out = variable[0]
        for i in range(2,len(variable)):
            out /= variable[i]
    return out


def f(input_string):
    p = re.compile('\(([\+\-\*\/])\s(:?[^\(^\).]+)\)')
    m = p.search(input_string)
    out = eval(m.group(1),m.group(2))
    output_string = input_string.replace(m.group(), str(out))
    try:
        f(output_string)
    except:
        print(output_string)
        pass

input_string = '(* (- 32 3) (- 32 4 8))'
f(input_string)

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

아, LISP의 사칙 연산은 단순한 이항연산이 아니었네요;; 죄송합니다. 문제를 뜨문뜨문 보는 바람에 잘못 풀었네요...

검색해보니 LIST의 연산자는 뒤에 몇 개의 피연산자가 오는지에 따라서 다르게 작동하네요.

  • (+ 1) : 단항연산자로 동작
  • (+ 1 2) : 이항연산자로 동작
  • (+ 1 2 3...) : 피연산자를 리스트로 보고 이를 fold함.

Swift3으로 다시 작성해봤습니다. 이곳에서 확인할 수 있습니다.

풀이한 과정은 이렇습니다.

  1. 수식의 기본 형태는 여는괄호, 바로다음에 연산자, 그 이후로 공백으로 나뉘어지는 피연산자..., 닫는 괄호
  2. 이 때 피연산자는 역시 괄호로 둘러싸인 수식일 수 있음

이를 파싱하면 (연산자, [피연산자의 리스트]) 형식의 데이터를 얻게 됩니다.

기본적으로 피연산자가 정수라 가정하고 커서를 옮겨가면서 정수값으로 파싱합니다. 그러다 중간에 여는 괄호를 다시 만나면 재귀호출을 통해서 중첩된 수식 부분을 파싱합니다. 파싱된 결과는 재귀 enum 타입으로 처리했고, 평가는 이 타입의 메소드로 구현했습니다.

enum Expression {
    case op(Character)
    case number(Int)
    indirect case operand(Expression, [Expression])

    func evaluate() -> Int? {

        func operation(_ x: Character) -> ((Int?, Int) -> Int?)? {
            let op: (Int, Int) -> Int?
            switch x {
            case "*": op = { $0 * $1 }
            case "/": op = { x, y in return y != 0 ? x / y : nil }
            case "+": op = { $0 + $1 }
            case "-": op = { $0 - $1 }
            default: return nil
            }
            return { x, y in 
                guard let x = x else { return nil }
                return op(x, y) 
            }
        }

        switch self {
        case let .number(i): return i 
        case let .operand(.op(x), values):
            guard values.count > 0 else { return 0 }
            guard let ops = operation(x) else { return nil }
            let vs = values.flatMap{ $0.evaluate() }
            return vs.dropFirst().reduce(vs[0], ops)

        default: return nil
        }
    }

}

func parse(expr: String, at index: String.Index? = nil) -> (Expression?, String.Index) {
    var cursor = index ?? expr.startIndex
    var operands: [Expression] = []

    guard expr[cursor] == "(" else { return (nil, cursor) }

    cursor = expr.index(after:cursor)
    let op: Expression = Expression.op(expr[cursor])
    var nodeStart = expr.index(after:cursor)

    while expr[cursor] != ")" && cursor < expr.endIndex {

        if expr[cursor] == " " { 
            if let i = Int(expr[nodeStart..<cursor]) {
                operands.append(.number(i))
            }
            nodeStart = expr.index(after:cursor)
        }
        else if expr[cursor] == "(" {
            let (subexpr, nextposition) = parse(expr:expr, at:cursor)
            if let subexpr = subexpr { operands.append(subexpr) }
            nodeStart = nextposition
            cursor = expr.index(after:nodeStart)
            continue
        }
        cursor = expr.index(after: cursor)
    }
    if nodeStart < cursor, let i = Int(expr[nodeStart..<cursor]) {
        operands.append(.number(i))
    }
    return (Expression.operand(op, operands), cursor)
}

let s = "(+ 10  9 8 (* 5 4) 7 (/ 8 2) 6)"
if case let (s?, _) = parse(expr:s), let result = s.evaluate() {
    print(result)
} else {
    print("invalid expression")
}


일단 입력에는 오류가 없다고 가정하고 시작합니다. LISP 표현식은 전위식 표기와 동치이기 때문에 사실상 괄호는 무시해도 됩니다. 따라서 괄호를 제외한 문자들을 공백으로 나누고 연산자와 피연산자를 구분, (피연산자는 정수만) 연산자는 문자 그대로, 피연산자는 정수로 변환해준 후 이를 뒤집어서 스택으로 만듭니다. (사실 .pop(0) 해도 되기 때문에 뒤집지 않아도 됩니다.)

평가방식은 다음과 같습니다.

  1. 스택에서 토큰을 하나 꺼냅니다. 토큰이 정수이면 토큰은 그 값 그대로 평가됩니다.
  2. 토큰이 연산자라면 하나의 값을 더 꺼내어 평가하고, 다시 한 번 더 값을 꺼내어 평가합니다. 그런 다음 두 값에 연산자마다 약속된 연산을 적용하여 리턴합니다.
  3. 2에서 평가중에 연산자가 튀어나온다면 2를 재귀적으로 호출합니다.


def do(s=None):
    ops = {
        '*': lambda x, y: x * y,
        '/': lambda x, y: x / y,
        '+': lambda x, y: x + y,
        '-': lambda x, y: x - y,
    }

    def getInput():
        nonlocal s
        if s is not None:
            inp = s
        else:
            inp = input()
        inp = ''.join(x for x in inp if x not in '()').split()
        temp = []
        for token in inp:
            if token.isdigit() or (token[0] == '-' and token[1:].isdigit()):
                temp.append(int(token))
            elif token in '+-/*':
                    temp.append(token)
        return temp[::-1]

    def evaluate(st):
        x = st.pop()
        if isinstance(x, int):
            return x, st
        if x in ops:
            a, st = evaluate(st)
            b, st = evaluate(st)
            return ops[x](a, b), st

    return evaluate(getInput())[0]


print(do('(- 10 3)'))
전위식 표현식과 LISP 표현식은 다르기 때문에 전위식을 가정하고 푸신다면 답이 달라집니다. (- 10 3 5) 과 같은 경우도 있구요.. - Han Jooyung, 2016/11/14 22:30 M D
Swift를 잘 모르지만 case에 op는 빼도 좋을 것 같네요. 그리고 parse 함수의 while 에서 expr[cursor] != ")" && cursor < expr.endIndex 조건 식은 순서가 바뀐 것 같아요. (물론 이 문제에서는 상관없지만..) - Han Jooyung, 2016/12/01 16:41 M D
네 말씀대로 op를 case에서 빼고 표현식 타입을 단일값 | (연산자, 피연산자) 의 형태로만 구분하는게 더 깔끔할 듯 합니다. 그리고 지적하신 검사 순서는 수정해야 하겠네요. endIndex는 시퀀스의 길이값과 일치해서 문제가 됩니다. - 룰루랄라, 2016/12/14 16:17 M D
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

댓글을 본 뒤 수정했습니다. p.s. 그러고보니 그냥 스택을 쓸껄 그랬군요..


#include <stdio.h>
#include <string.h>
#include <iostream>

using namespace std;

#define PLUS 0
#define MINU 1
#define MULT 2
#define DIVD 3

int pos;

float Lisp(string input)
{
    float result = 0;
    int mark = -1;

    float nFirstNum = 0.0;  //앞 숫자    
    float nSecondNum = 0.0; //뒷 숫자
    float returnResult = 0.0;
    bool bFristInput = false;
    bool bSecondInput = false;
    //printf("input: %s\n", input.c_str());

    while(1)
    {
        //입력받은 수식의 끝 체크
        if(pos >= input.length())
        {            
            break;
        }

        //닫는 괄호 연산 끝 리턴
        if(input[pos] == ')')
            break;

        //여는 괄호가 나오면 다시 함수 호출
        if(input[pos] == '(')
        {
            pos++;
            returnResult = Lisp(input);

            if(!bFristInput)
            {
                nFirstNum = returnResult;
                bFristInput = true;
            }
            else
            {
                nSecondNum = returnResult;
                bSecondInput = true;
            }
        }

#pragma region 부호결정
        //부호 결정
        if(mark == -1)//부호가 아직 결정이 안됐다면
        {
            if(input[pos] == '+') 
                mark = PLUS;
            else if(input[pos] == '-' )
                mark = MINU;
            else if(input[pos] == '*' )
                mark = MULT;
            else if(input[pos] == '/' )
                mark = DIVD;
        }
#pragma endregion

#pragma region 문자열을 숫자로
        //숫자 범위면
        if(input[pos] >= '0' && input[pos] <= '9')
        {
            int i = 0;
            //첫 번째 숫자가 비어있으면
            if(!bFristInput)
            {
                for(i = pos; input[i] >= '0' && input[i] <= '9'; i++)
                {
                    nFirstNum *= 10; // 자리수 증가
                    nFirstNum += input[i] - '0';
                }
                bFristInput = true;
            }
            //두 번째 숫자를 구한다.
            else
            {
                for(i = pos; input[i] >= '0' && input[i] <= '9'; i++)
                {
                    nSecondNum *= 10; // 자리수 증가
                    nSecondNum += input[i] - '0';
                }
                bSecondInput = true;
            }
            pos = i - 1;
        }
#pragma endregion

#pragma region 연산
        //연산
        if(bSecondInput)
        {
            switch(mark)
            {
            case PLUS:
                //printf("%d + %d\n", nFirstNum, nSecondNum);
                nFirstNum += nSecondNum;
                break;
            case MINU:
                //printf("%d - %d\n", nFirstNum, nSecondNum);
                nFirstNum -= nSecondNum;
                break;
            case MULT:
                //printf("%d * %d\n", nFirstNum, nSecondNum);
                nFirstNum *= nSecondNum;
                break;
            case DIVD:
                if(nSecondNum == 0)
                    return -999;
                nFirstNum /= nSecondNum;
                break;
            }
            nSecondNum = 0;
            bSecondInput = false;
        }
#pragma endregion

        pos++;

        result = nFirstNum;

    }
    //printf("return: %d\n", result);
    return result;
}

int main (int argc, char *argv[])
{
    string input[7];
    input[0]= "(* (+ 2 3) (- 5 3))";
    input[1] ="(/ (+ 9 1) (+ 2 3))";
    input[2] = "(* (- 10 3 5) (+ 2 5) (/ 10 2))";
    input[3] = "(/ (* 12 12 12 12) (* 2 6) (/ 10 5))";
    input[4] = "(+ (+ (- 3 5) (* 1 3)) (+ 2 5))";
    input[5] = "(* (/ (+ (- 3 5) (+ 4 1)) (+ 1 1)) (- 1 2)) ";
    input[6] = "(+ (* 2 2 2 2) (/ 64 2 2 2))";

    int i = 0; 
    for(i = 0; i < 7; i ++)
    {
        pos = 0;
        printf("result: %.3f\n", Lisp(input[i]));
    }
    return 0;
}
괄호가 3번 이상 중첩된 경우에 올바른 계산이 안되는 것 같습니다. 중첩된 괄호를 만나서 Lisp()으로 계산한 다음 바로 )를 찾는게 문제 아닐지.. 짝이 맞는 괄호를 찾아야 하죠. - Han Jooyung, 2016/11/14 22:34 M D
네 확인해보겠습니다. - 황 승태, 2016/11/15 14:29 M D
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

첫번째 방법: 정규식 이용

import re
run = lambda e, *_tuple: str(eval(e.join(_tuple)))
ins = lambda _string, start, end: _string[:start] + '"' + _string[start:end] + '"' + _string[end:]
while __name__ == '__main__':
    s = input('>>>')
    for i in reversed([*re.finditer(r'([^() ]+)', s)]):
        s = ins(s, *i.span())
    for i in [('(', 'run('), ' ,']:
        exec('s = s.replace("%s", "%s")'%(*i,))
    print(eval(s))

두번째 방법: 정규식 없음

def lisp_eval(args):
    return eval(args[0].join(args[1:]))

def divide_eval(_list):
     res = []
     k = 0
     for n, i in enumerate(_list):
          if i == '(':
               k += 1
          if i == ')':
               k -= 1
          if i == ' ' and k == 0:
              res.append(n)
     return res

def divide(_list):
     res = []
     s = _list[:]
     target = reversed(sorted(divide_eval(_list)))
     for i in target:
          res.append(s[i+1:])
          s = s[:i]
     res.append(_list[0])
     res.reverse()
     return res

def interpret(s):
     if len(s) == 3:
          return 0
     s = s[1:-1]
     s_list = divide(s)
     for i in range(1, len(s_list)):
          if '(' in s_list[i]:
               s_list[i] = str(interpret(s_list[i]))
     return lisp_eval(s_list)

while __name__ == '__main__':
     print(interpret(input('>>>')))

파이썬 3.5.2 64

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

Ruby

eval 사용(풀이1), 스택 구현(풀이2). 두가지로 풀이. (수정 : 풀이 2 추가)

풀이 1. s-expression을 람다 약기로 변환한 뒤 eval.

calc = proc {|op,*args| args.reduce(op) || 0 }
lisp_eval = ->exp { eval exp.gsub(/[(\s)]/, '('=>"calc[:", ' '=>',', ')'=>']') }

풀이 2. 토큰을 차례차례 스택에 push. 토큰이 ")"면 스택에서 직전의 연산자까지 꺼내서 계산. 이를 반복.

calc = proc {|op,*args| args.reduce(op) || 0 }
eval_top = ->s { t=[]; t.unshift(s.pop) until t[0].is_a? Symbol; s << calc[*t] }
lisp_eval = ->str do
  tokens = str.gsub(/[()]/, "("=>"",")"=>" )").split.
               map {|e| e == ")" ? e : e =~ /[[:digit:]]/ ? e.to_i : e.to_sym }
  tokens.reduce([]) {|stack,e| e == ")" ? eval_top[stack] : stack << e }.pop 
end

Test

# tests : arity 1, 3, 4, nested s-exp, complex s-exp
cases = ["(+)"] +
        ["(- 10 3)", "(* 2 3)"] +  
        ["(- 10 3 5)", "(* 2 3 4)"] + 
        ["(* (+ 2 3) (- 5 3))", "(/ (+ 9 1) (+ 2 3))"] +
        ["(* 1 (- 2 3) 4 (+ 2 -1) 3)" ]
expect( cases.map(&lisp_eval) ).to eq [0, 7, 6, 2, 24, 10, 2, -12]

Output

lisp_eval["(+ 2 3 5 (* 2 5) (* -2 5))"] #=> 10
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

아래의 함수를 만들면 될 것 같다.

int eval(const char* s);

그런데 리스트를 파싱하는 함수가 (+ 1 (- 1 2) 3)를 처리한다면, 중첩된 (- 1 2)에 대해서 재귀적으로 호출할 수 있어야 할 것 같다. 이때, 문자열 전체를 처리하지 않을 것이고 닫힌 괄호까지만 처리하면 된다. 그러면 원래의 리스트를 처리하는 함수는 파싱하고 남은 부분 3)을 재귀호출 함수에서 받아올 수 있어야 한다. 즉, 입력 커서 역할을 하는 const char* s만 전달해서는 소용없고 함수 호출하여 이 값을 업데이트 해야 한다. 이중포인터로 전달하는 것도 방법이겠지만 context라고 감싸서 전달하는 것이 낫다.

typedef struct context context_t;

struct context {
    const char * s;
};

int eval(context_t* c);

그러면 main()은 다음처럼 만들어볼 수 있다. (free는 생략)

context_t* context(const char* s) {
    context_t* c = (context_t*)malloc(sizeof(context_t));
    c->s = s;
    return c;
}

int main(int argc, const char * argv[]) {
    printf("%d\n", eval(context("1")));
    printf("%d\n", eval(context("123")));
    printf("%d\n", eval(context("(+)")));
    printf("%d\n", eval(context("(+ 2 3)")));
    printf("%d\n", eval(context("(+ 1 2)")));
    printf("%d\n", eval(context("(* 1 2 (- 1 2 -3))")));

    return 0;
}

간단한 양의 정수만 고려해보자.

int eval(context_t* c) {
    return num(c);
}

int num(context_t* c) {
    int n = 0;
    while (isdigit(*c->s)) {
        n *= 10;
        n += *c->s - '0';
        c->s++;
    }
    return n;
}

음의 정수까지 고려한다면..

int eval(context_t* c) {
    if (isdigit(*c->s))
        return num(c);
    if (*c->s == '-') {
        ++c->s;
        return -num(c);
    }

    return 0;
}

드디어 리스트를 처리해보자

int eval(context_t* c) {
    if (isdigit(*c->s))
        return num(c);
    if (*c->s == '-') {
        ++c->s; // skip -
        return -num(c);
    }

    assert(*c->s == '(');
    ++c->s; // skip (
    return list(c);
}

list() 는 첫 항이 +,-,*,/ 여야 한다. 나머지는 공백을 건너뛰고 닫힌 괄호까지 처리한다. 그런데 -는 첫 항에서 나머지를 빼고, / 는 첫 항에서 나머지를 나눠나간다.

void spaces(context_t* c) {
    while (*c->s == ' ')
        c->s++;
}

int list(context_t* c) {
    char op = *c->s++;
    int value;

    if (op == '-' || op == '/') { // should have 1+ args
        spaces(c);
        value = eval(c);
    } else if (op == '+') {
        value = 0;
    } else {
        value = 1;
    }

    while (*c->s != ')') {
        spaces(c);
        value = calc(op, value, eval(c));
    }
    ++c->s; // skip )

    return value;
}
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

풀이 작성

※ 풀이작성 안내
  • 본문에 코드를 삽입할 경우 에디터 우측 상단의 "코드삽입" 버튼을 이용 해 주세요.
  • 마크다운 문법으로 본문을 작성 해 주세요.
  • 풀이를 읽는 사람들을 위하여 풀이에 대한 설명도 부탁드려요. (아이디어나 사용한 알고리즘 또는 참고한 자료등)
  • 작성한 풀이는 다른 사람(빨간띠 이상)에 의해서 내용이 개선될 수 있습니다.
목록으로
코딩도장

코딩도장은 프로그래밍 문제풀이를 통해서 코딩 실력을 수련(Practice)하는 곳입니다.

recursive descent parser x 1

언어별 풀이 현황
전 체 x 6
python x 3
cpp x 1
기 타 x 1
ruby x 1