변경이력

돌아가기
5 49개 문자 추가 8개 문자 삭제

2016/11/24 08:37

룰루랄라

아, LISP의 사칙 연산은 단순한 이항연산이 아니었네요;; 죄송합니다. 문제를 뜨문뜨문 보는 바람에 잘못 풀었네요... 검색해보니 LIST의 연산자는 뒤에 몇 개의 피연산자가 오는지에 따라서 다르게 작동하네요. * `(+ 1)` : 단항연산자로 동작 * `(+ 1 2)` : 이항연산자로 동작 * `(+ 1 2 3...)` : 피연산자를 리스트로 보고 이를 fold함. Swift3으로 다시 작성해봤습니다. [이곳](http://swiftlang.ng.bluemix.net/#/repl/5836a3dcdcb5f43d4f9395f8)에서 확인할 수 있습니다. 풀이한 과정은 이렇습니다. 1. 수식의 기본 형태는 여는괄호, 바로다음에 연산자, 그 이후로 공백으로 나뉘어지는 피연산자..., 닫는 괄호 2. 이 때 피연산자는 역시 괄호로 둘러싸인 수식일 수 있음 이를 파싱하면 (연산자, [피연산자의 리스트]) 형식의 데이터를 얻게 됩니다. 기본적으로 피연산자가 정수라 가정하고 커서를 옮겨가면서 정수값으로 파싱합니다. 그러다 중간에 여는 괄호를 다시 만나면 재귀호출을 통해서 중첩된 수식 부분을 파싱합니다. 파싱된 결과는 재귀 enum 타입으로 처리했고, 평가는 이 타입의 메소드로 구현했습니다. ```{.swift} 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, at:nil), let result = s.evaluate() { print(result) } else { print("invalid expression") } ``` ---- 일단 입력에는 오류가 없다고 가정하고 시작합니다. LISP 표현식은 전위식 표기와 동치이기 때문에 사실상 괄호는 무시해도 됩니다. 따라서 괄호를 제외한 문자들을 공백으로 나누고 연산자와 피연산자를 구분, (피연산자는 정수만) 연산자는 문자 그대로, 피연산자는 정수로 변환해준 후 이를 뒤집어서 스택으로 만듭니다. (사실 `.pop(0)` 해도 되기 때문에 뒤집지 않아도 됩니다.) 평가방식은 다음과 같습니다. 1. 스택에서 토큰을 하나 꺼냅니다. 토큰이 정수이면 토큰은 그 값 그대로 평가됩니다. 2. 토큰이 연산자라면 하나의 값을 더 꺼내어 평가하고, 다시 한 번 더 값을 꺼내어 평가합니다. 그런 다음 두 값에 연산자마다 약속된 연산을 적용하여 리턴합니다. 3. 2에서 평가중에 연산자가 튀어나온다면 2를 재귀적으로 호출합니다. ```{.python} 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의 사칙 연산은 단순한 이항연산이 아니었네요;; 죄송합니다. 문제를 뜨문뜨문 보는 바람에 잘못 풀었네요... 검색해보니 LIST의 연산자는 뒤에 몇 개의 피연산자가 오는지에 따라서 다르게 작동하네요. * `(+ 1)` : 단항연산자로 동작 * `(+ 1 2)` : 이항연산자로 동작 * `(+ 1 2 3...)` : 피연산자를 리스트로 보고 이를 fold함. Swift3으로 다시 작성해봤습니다. [이곳](http://swiftlang.ng.bluemix.net/#/repl/5836a3dcdcb5f43d4f9395f8)에서 확인할 수 있습니다. 풀이한 과정은 이렇습니다. 1. 수식의 기본 형태는 여는괄호, 바로다음에 연산자, 그 이후로 공백으로 나뉘어지는 피연산자..., 닫는 괄호 2. 이 때 피연산자는 역시 괄호로 둘러싸인 수식일 수 있음 이를 파싱하면 (연산자, [피연산자의 리스트]) 형식의 데이터를 얻게 됩니다. 기본적으로 피연산자가 정수라 가정하고 커서를 옮겨가면서 정수값으로 파싱합니다. 그러다 중간에 여는 괄호를 다시 만나면 재귀호출을 통해서 중첩된 수식 부분을 파싱합니다. 파싱된 결과는 재귀 enum 타입으로 처리했고, 평가는 이 타입의 메소드로 구현했습니다. ```{.swift} 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, at:nil), let result = s.evaluate() { print(result) } else { print("invalid expression") } ``` ---- 일단 입력에는 오류가 없다고 가정하고 시작합니다. LISP 표현식은 전위식 표기와 동치이기 때문에 사실상 괄호는 무시해도 됩니다. 따라서 괄호를 제외한 문자들을 공백으로 나누고 연산자와 피연산자를 구분, (피연산자는 정수만) 연산자는 문자 그대로, 피연산자는 정수로 변환해준 후 이를 뒤집어서 스택으로 만듭니다. (사실 `.pop(0)` 해도 되기 때문에 뒤집지 않아도 됩니다.) 평가방식은 다음과 같습니다. 1. 스택에서 토큰을 하나 꺼냅니다. 토큰이 정수이면 토큰은 그 값 그대로 평가됩니다. 2. 토큰이 연산자라면 하나의 값을 더 꺼내어 평가하고, 다시 한 번 더 값을 꺼내어 평가합니다. 그런 다음 두 값에 연산자마다 약속된 연산을 적용하여 리턴합니다. 3. 2에서 평가중에 연산자가 튀어나온다면 2를 재귀적으로 호출합니다. ```{.python} 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)')) ```
4 315개 문자 추가

2016/11/24 08:34

룰루랄라

3 2763개 문자 추가

2016/11/24 08:29

룰루랄라

2 37개 문자 추가

2016/11/14 06:01

룰루랄라

1 Original

2016/11/14 05:59

룰루랄라

코딩도장

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