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

2개의 풀이가 있습니다.

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

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스택에 다시
담아 연산을 한뒤 다시 되돌려주는 방법으로 했습니다.
*/

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

풀이 작성

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

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

recursive descent parser x 1

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