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

1개의 풀이가 있습니다.

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

풀이 작성

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

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

recursive descent parser x 1

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