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
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

12개의 풀이가 있습니다. 1 / 2 Page

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

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;
}
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

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
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

첫번째 방법: 정규식 이용

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

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

댓글을 본 뒤 수정했습니다. 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
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

아, 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
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
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)

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

C(99)
gcc -std=c99 -pedantic-errors -W -Wall

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <stdbool.h>
#include <assert.h>

// TokenStream 구조체
typedef enum _type { OPERATOR, NUMBER } Type; // 연산자와 숫자 타입
typedef struct _token
{
    Type type;
    int content; 
} Token;
typedef struct _tokenStrem
{
    Token tokenArray[100];
    int cursor; // 토큰스트림의 현재 가리키고 있는 인덱스
    int size; // 토큰스트림 사이즈
} TokenStream;

// Stack 구조체
typedef struct _stack
{
    Token arr[100]; // 토큰으로 이뤄진 배열스택
    int cur; // 현재 가리키고 있는 인덱스
} Stack;

static TokenStream ts; // TokenStream은 접근하기 쉽게 전역변수로 선언

// TokenStream Operator
Token GetToken(void);
void InitTokenStream(const char * expr);
void ShowToken(Token t);
void ShowTokenStream(void); // 디버깅용

// Stack Operator
Stack * StackInit(void);
void StackPush(Stack * pstack, Token t);
Token StackPop(Stack * pstack);
bool StackIsEmpty(Stack * pstack);

Token Calc(void)
{
    Token tmp, left, right, op;
    Stack * peek = StackInit(); // 일단 담는다
    Stack * calc = StackInit(); // ')'을 만나면 '('까지 따로 담아 계산한다
    while (ts.cursor < ts.size)
    {
        tmp = GetToken();
        while (tmp.content != ')')
        {
            StackPush(peek, tmp);   
            tmp = GetToken();
        }
        // tmp.content == ')'...')' 버려짐
        while (tmp.content != '(')
        {
            tmp = StackPop(peek);
            StackPush(calc, tmp); // 계산하기위한 스택에 넣는다
        }
        // tmp.content == '('
        StackPop(calc); // '(' 버림

        op = StackPop(calc); // 한항의 연산자
        left = StackPop(calc); // 첫번째 숫자
        while (! StackIsEmpty(calc))
        {
            right = StackPop(calc);
            switch (op.content)
            {
                case '+': left.content = left.content + right.content; break;
                case '-': left.content = left.content - right.content; break;
                case '*': left.content = left.content * right.content; break;
                case '/': left.content = left.content / right.content; break;
                default: assert(0);
            }
        }
        // calc 스택이 비었음
        StackPush(peek, left); // 한항을 계산한 결과는 peek 스택에 다시 푸시
    }
    // TokenStream이 끝남
    return left;
}

int main(void)
{
    const char * expr1 = "(* (+ 1 1 3) (- 3 1) (+ 1 4) )";
    printf("%s = ", expr1);
    InitTokenStream(expr1);
    ShowToken(Calc());

    const char * expr2 = "(/ (+ 9 1) (+ 2 3))";
    printf("%s = ", expr2);
    InitTokenStream(expr2);
    ShowToken(Calc());

    const char * expr3 = "(- 10 3 5)";
    printf("%s = ", expr3);
    InitTokenStream(expr3);
    ShowToken(Calc());

    const char * expr4 = "(* (+ 2 3) (- 5 3))";
    printf("%s = ", expr4);
    InitTokenStream(expr4);
    ShowToken(Calc());

    return 0;
}

// 토큰스트림에서 토큰 하나를 받음
Token GetToken(void) { return ts.tokenArray[ts.cursor++]; }

// 문자열을 TokenStream으로 변환
void InitTokenStream(const char * expr)
{
    Token tmpToken;
    int tmpNum;
    int i = 0;

    while (*expr)
    {
        if (isdigit(*expr))
        {
            sscanf(expr, "%d", &tmpNum);    
            tmpToken.type = NUMBER;
            tmpToken.content = tmpNum;
            ts.tokenArray[i++] = tmpToken;
            while (isdigit(*expr))
                expr++;
        }

        else if (isspace(*expr))
        {
            expr++;
        }

        else
        {
            tmpToken.type = OPERATOR;
            tmpToken.content = *expr;
            ts.tokenArray[i++] = tmpToken;
            expr++;
        }
    }
    ts.size = i;
    ts.cursor = 0;
}

// Token 하나를 타입에 맞게 출력한다
void ShowToken(Token t)
{
    if (t.type == OPERATOR)
        printf("%c \n", t.content);
    else
        printf("%d \n", t.content);
}

// 토큰스트림이 잘 됐는지 확인하는 디버깅용
void ShowTokenStream(void)
{
    int i;
    for (i = 0; i < ts.size; i++)
    {
        if (ts.tokenArray[i].type == OPERATOR)
            printf("[OPERATOR] %c \n", ts.tokenArray[i].content);
        else
            printf("[NUMBER] %d \n", ts.tokenArray[i].content);
    }
    printf("TokenStream size = %d \n", ts.size);
    putchar('\n');
}

// 스택 초기화
Stack * StackInit(void)
{
    Stack * ret = malloc(sizeof (Stack));
    ret->cur = -1;
    return ret;
}

void StackPush(Stack * pstack, Token t)
{
    pstack->arr[++pstack->cur] = t; 
}

Token StackPop(Stack * pstack) { return pstack->arr[pstack->cur--]; }

bool StackIsEmpty(Stack * pstack) { return pstack->cur == -1; }
/* 
문자열을 토큰으로 쪼개어 토큰스트림을 만듭니다.
토큰스트림에서 토큰 하나씩을 받아 peek 스택에 담습니다.
')' 토큰을 만나면 peek 스택에 담아둔 토큰중 '('를 만날때까지 calc 스택으로 push하고,
peek 스택에서는 pop을 합니다.
calc 스택에서는 스택이 빌때까지 계산을 한뒤 peek스택으로 push합니다.
스택을 두개 사용하여 한곳에서는 임시로 토큰을 받고, ( )사이의 숫자와 연산자는 calc스택에 다시
담아 연산을 한뒤 다시 되돌려주는 방법으로 했습니다.
*/

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
def func(s):
    nums,X = list(), 0
    for y in range(len(s)):
        if s[y].isnumeric() and y > X:
            tmp,c = s[y],1
            while s[y+c].isnumeric():
                tmp += s[y+c]
                c += 1
                X = y+c
            nums.append(tmp)
    return str(eval(s[1].join(nums)))

l,r = -1,-1
s_list = ['(- 10 3)','(- 10 3 5)','(* 2 3)',\
          '(* 2 3 4)','(* (+ 2 3) (- 5 3))','(/ (+ 9 1) (+ 2 3))']
for string in s_list:
    while '(' in string:
        for x in range(len(string)):
            if string[x] == '(':
                l = x
            elif string[x] == ')':
                r = x
                string = string[:l]+func(string[l:r+1])+string[r+1:]
                break
    print(string)

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

이제 막 String 클래스를 배우는 초보라서 아는 방법으로 열심히 해봤습니다ㅠㅠ 문제점도 많지만....

package coading.lisp;

import java.util.*;

public class Lisp_v2 {
    public static void main(String[] args) {

        System.out.print("Lisp 연산식을 입력하세요 : ");
        Scanner robot = new Scanner(System.in);
        String input = robot.nextLine();

        while (true) {

            String tmp = input.substring(input.lastIndexOf("(", input.indexOf(")")) + 1, input.indexOf(")")) + " ";

            String tmp_num_s = "";
            List<Integer> tmp_num = new ArrayList<Integer>();

            char symbol = 0;
            for (int i = 0; i < tmp.length(); i++) {

                if ((tmp.charAt(i) == '+' || tmp.charAt(i) == '-' || tmp.charAt(i) == '*' || tmp.charAt(i) == '/')
                        && i == 0) {
                    symbol = tmp.charAt(i);

                } else if (tmp.charAt(i) != ' ') {
                    if (tmp.charAt(i) != ')') {
                        tmp_num_s += tmp.charAt(i);
                    }

                } else {

                    if (tmp_num_s != "") {
                        tmp_num.add(Integer.decode(tmp_num_s));
                        tmp_num_s = "";
                    }
                }
            }

            int temp = tmp_num.get(0);
            for (int i = 1; i < tmp_num.size(); i++) {
                switch (symbol) {
                case '+':
                    temp += tmp_num.get(i);
                    break;
                case '-':
                    temp -= tmp_num.get(i);
                    break;
                case '*':
                    if (tmp_num.get(i) != 0)
                        temp *= tmp_num.get(i);
                    else
                        temp *= 1;
                    break;
                case '/':
                    if (tmp_num.get(i) != 0)
                        temp /= tmp_num.get(i);
                    else
                        temp /= 1;
                    break;
                }
            }

            System.out.println(input.replace("(" + tmp.trim() + ")", String.valueOf(temp)));

            input = input.replace("(" + tmp.trim() + ")", String.valueOf(temp));
            if (input.indexOf('(') == -1) {
                break;
            }
        }
    }
}

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
import java.util.ArrayList;
import java.util.List;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class LISPCalculator {

    static Node root = null;
    static Node current = null;
    static Node key = null;

    public static void main(String[] args) {
        final String ss = "(* (+ 2 3) (- 5 3))";
        final Pattern p = Pattern.compile("\\*|\\+|/|-(?!\\d)|-?\\d{1,30}|\\)");
        final Matcher m = p.matcher(ss);

        while (m.find()) {
            final String mg = m.group();
            if (mg.equals("*") || mg.equals("/") | mg.equals("+") | mg.equals("-")) {
                Node node = new Node(mg, new ArrayList<>());
                if (root == null) {
                    root = node;
                    current = node;
                    key = node;
                } else if (current.left == null) {
                    current.left = node;
                    node.parent = current;
                    key = node;
                } else if (current.right == null) {
                    current.right = node;
                    node.parent = current;
                    key = node;
                    current = current.left;
                }
            } else if (mg.equals(")")) {
                if (current.parent != null) current = current.parent;
                key = current;
            } else {
                key.numbers.add(Integer.valueOf(mg));
            }
        }

        recursive(root);
        String o = root.operation;
        System.out.println(root.numbers.stream().reduce((a, b) -> operation(a, b, o)).orElse(0));
    }

    private static void recursive(Node node) {
        if (node == null) return;
        recursive(node.left);
        recursive(node.right);
        node.result = node.numbers.stream().reduce((a, b) -> operation(a, b, node.operation)).orElse(0);
        if (node != root) node.parent.numbers.add(node.result);
    }

    private static Integer operation(Integer a, Integer b, String o) {
        if (o.equals("+")) return a + b;
        if (o.equals("-")) return a - b;
        if (o.equals("*")) return a * b;
        if (o.equals("/")) return a / b;
        return 0;
    }
}

class Node {
    Node left;
    Node right;
    Node parent = null;
    String operation;
    List<Integer> numbers;
    Integer result = 0;

    public Node(String operation, List<Integer> numbers) {
        this.operation = operation;
        this.numbers = numbers;
    }
}
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

풀이 작성

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

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

recursive descent parser x 1

언어별 풀이 현황
전 체 x 12
기 타 x 2
ruby x 1
python x 4
cpp x 2
java x 2
cs x 1