스택 계산기

프로그래밍 2008.01.05 01:31
새해 첫 포스팅은...
괄호와 연산자 우선순위가 적용되는 계산기 만들기..;;;;

며칠 전, 연산자와 괄호의 우선순위를 인식하는 계산기가 필요하다는 누군가의 요청에 의해 작성하게 되었음. 문제를 듣자 마자 학교에서 자료구조 시간에 배웠던 '스택을 이용한 수식계산'이 떠올랐음.

사실 자료구조 기말고사 문제로 출제되었던 내용이라 어렴풋이 기억이 있었는데, 이런 곳에 써먹을 줄은 꿈에도 몰랐다. 당시엔 스택을 이용한 수식계산을 보고, '이렇게 계산하는 방법도 있구나...'라고 생각만 하고 그냥 대강 넘어갔었는데...;;


수식은 일반적으로 3가지 표기법으로 표현할 수 있다.

연산자가 피연산자 가운데 위치하는 중위 표기법(infix notation)  ex> 2 + 5
연산자가 피연산자 앞에 위치하는 전위 표기법(prefix notation)   ex> + 2 5
연산자가 피연산자 뒤에 위치하는 후위 표기법(postfix notation)  ex> 2 5 +

여기서 후위 표기법은 폴랜드 논리학자 Jan Lucasiewicz에 의해 고안되었기 때문에 폴리쉬 표기법(polish notation)이라고도 한다.

후위 표기식은 다음과 같은 두 가지 이점을 가지고 있다.

1. 연산자 우선순위와 관계없이 왼편에서 오른편으로 연산자가 기술된 순서대로 일관되게 계산을 하면 되기 때문에, 연산 순서가 간단하다.
2. 연산 순서를 변경시키는 괄호를 사용하지 않는다. 이런 이점으로 컴퓨터 내부에서는 이 후위 표기법을 사용한다.

라고 책에 나와있다;;;


코드를 만들면서 느낀점.

자바는 API에 있는 스택 덕분에 직접 구현하지 않아도 되어서 무지 편했다.(직접 스택을 구현하라고 했다면 시간도 더 들고, 코드의 양도 늘어났을 것임)

입력받은 식을 후위 표기법으로 변환하기만 한다면 수식을 연산 하는 것은 무지 쉽다.

혼자서 계산기를 만들라고 했다면 힘들었겠지만, 다행이 내겐 '자료구조'책이 있었다.


Calc.java

자바소스

input.jsp

입력받는 폼, JSP로 폼 하나만 덩그러니..ㅋㅋ

proc.jsp

결과를 보여주는 팝업



자세한 알고리즘을 모두 정리하려면 그림도 있어야 하고 복잡하니, 대강 만든 소스만 일단 올려놓아 본다. 나중에 내가 쓰게 될지도 모르니까.S
top
  1. 지누 2015.01.14 15:24 신고 수정/삭제 댓글

    잘봤습니다 ㅋㅋ근데 대괄호([])까지 들어갈려면 어디에 어떻게 넣어야 할까요??

댓글 쓰기

연결리스트와 스택 과제

프로그래밍 2007.10.04 01:44
  블로그에 코드는 다시는 올리지 않으려고 했는데 에라~ 모르겠다~

  오늘 자주 들르는 커뮤니티에 고민 글이 하나 올라왔다. 고민인즉!!
  전공수업에서 교수님이 C언어 과제를 하나 내 주셨다.

문제> "단어1 단어2 단어3 단어4" 를 입력받으면 스택과 연결리스트를 이용하여          저장한후
         "단어4 단어3 단어2 단어1"의 형태로 출력을 하는 프로그램을 작성하시오.
 
e.g>입력 : I Love You
      출력 : You Love I

  자료구조 수업인 것 같은데 입력받은 문장을 공백을 기준으로 분리해서 스택에 과 연결리스트를 이용해 저장한 후 출력하는 문제이다.

  3년만에 학교를 복학해서 C언어와 자료구조 동강까지 보면서 공부를 해 봐도 풀리지가 않아서 고민 글을 쓰게 된 것이다. 얼마나 고민이 되었을까.. 문제는 안풀리고 마냥 답답했나보다..ㅠㅠ

  정말 도와주고 싶었지만... 코드를 C로 작성해야 한다는 제약사항이!! C언어는 2학년때 이후로 본지가 오래되어서 자주 쓰이는 함수들 이름조차 다 까먹었는데.....;;; 아... 슬프다. 도와줄 방법이 없구나. 문제를 딱 보니 스택은 LIFO(Last In, First Out)형태의 자료구조이니 스택에 먼저 입력받은 문장을 단어로 나누어 넣은 후 스택에 들어있는 단어들을 차례대로 꺼내서 연결리스트에 넣는 문제라는 감은 왔는데....

  그래서 미약하나마 힘이 되고자 가장 손에 익은 언어인 자바로 코드를 만들어서 답변으로 올려 두었다. 사실.. 자바나 C나 문법만 약간 다를뿐.. 내용물은 비슷비슷 할테니 힌트라도 되지 않을까 생각되었다.


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Stack;


public class Test {
   
    /**
     * 문자배열을 인수로 받아
     * 스택에 넣어 스택을 리턴
     * @param words
     * @return
     */
    public Stack pushStack(String[] words){
        Stack stack = new Stack();
        for(int i = 0; i < words.length; i++){
            stack.push(words[i]);
        }
        return stack;
    }
   
    /**
     * 스택을 인수로 받아
     * 연결리스트에 넣어 연결리스트를 리턴
     * @param stack
     * @return
     */
    public LinkedList addLinkedList(Stack stack){
        LinkedList linkedList = new LinkedList();
        while(!stack.empty()){
            linkedList.add(stack.pop());
        }
        return linkedList;
    }
   
    /**
     * 단어들을 입력받아 공백을 기준으로
     * 문자들을 배열에 저장
     * 배열을 리턴
     * @return
     * @throws IOException
     */
    public String[] inputWords() throws IOException{
        String[] words = null;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        try{
            System.out.print("입력 : ");
            words = br.readLine().split(" ");
        }catch(IOException e){
            System.out.println(e);
        }finally{
            if(br != null) br.close();
        }
       
        return words;
    }
   
    public static void main(String[] args) throws IOException {
        Test test = new Test();
       
        Stack stack = test.pushStack(test.inputWords());    //문자를 입력받아 스택에 저장
        LinkedList linkedList = test.addLinkedList(stack);    //스택의 값을 연결리스트에 저장
       
        //연결리스트의 값을 차례대로 출력
        System.out.print("출력 : ");
        for(int i = 0; i < linkedList.size(); i++){
            System.out.print(linkedList.get(i)+" ");
        }
    }

}


  도움이 되었으면 좋겠다. 정말루...;;

  만약 연결리스트와 스택도 직접 구현해서 사용해야 하는 문제라면, 어짜피 책에 간단한 스택과 연결리스트의 예제 소스가 있을테니 그걸 참고하면 될테고.. 문자열을 나누는 sprit()메소드는 C언어에도 비슷한 역할을 하는 함수가 있을테니 그걸 찾아다 쓰면 될 것 같다.

  부디 꼭 성공하세요!! 싸인펜이 응원합니다!!S

'프로그래밍' 카테고리의 다른 글

2007 JCO 오픈소스 컨퍼런스  (2) 2007.10.15
2007 JCO 오픈 소스 컨퍼런스 (10월13일)  (6) 2007.10.07
연결리스트와 스택 과제  (10) 2007.10.04
객체지향  (4) 2007.10.03
High Cohesion, Loose Coupling  (2) 2007.10.03
게시판 만들기 작업 진척도  (2) 2007.09.30
top
  1. Favicon of http://www.myhyuny.net/ 화현 2007.10.04 02:17 신고 수정/삭제 댓글

    저는 왜, "링크드 리스트로 스텍을 구현해서 문제를 해결하세요"로 들리죠... -_-;;;

    • Favicon of http://signpen.net 싸인펜 2007.10.04 02:36 신고 수정/삭제

      헉!! 문제가 그것일 수도 있겠네요..;;

      저희학교 교수님이 내 주신 문제라면 교수님께 문제를 다시한 번 여쭈어 볼 수도 있을텐데.. 그게 아니라서..;;

      화현님이 이해하신대로의 문제라면 연결리스트에 단어들을 넣을 때 마다 연결리스트의 첫번째 인덱스에 값을 추가하면 스택처럼 동작할것 같은데, 그렇게 문제를 풀어 나가야 할 것 같은데요.

      그 분.... 어떻하죠?? 덜덜덜...

  2. Favicon of http://mewmew.tistory.com 야옹*^^* 2007.10.04 21:12 신고 수정/삭제 댓글

    ^^;; 뭔지 모르지만.. 잘 도움이 되셨기를~!!
    모두 화이링~!!

    • Favicon of http://signpen.net 싸인펜 2007.10.05 01:11 신고 수정/삭제

      그 분께서 밤을 새워서라도 과제를 하겠다는 댓글을 확인했습니다^^ㅋ

      자바 소스이긴 하지만, 참고가 될 것 같다고 하시네요.

  3. erer 2007.10.04 23:59 신고 수정/삭제 댓글

    자바로 하셨는데 c++로 하는 법 알려주세요 아시는분은 제 메일
    ufo12_12@naver.com으로 보내주세여 급합니다 꼭 부탁드립니다

    • Favicon of http://signpen.net 싸인펜 2007.10.05 01:14 신고 수정/삭제

      C++은..... OTL

      제 컴퓨터에 C++컴파일러도 설치되어 있지 않고, 게다가 C나 C++쪽은 제가 약해서... 아마 한참 걸릴 것 같습니다...;;

      제가 도움이 되지 못할 것 같아요. 그런데 과제가 같은가봐요??

  4. Favicon of http://luminance.kr/ 루미넌스 2007.10.05 16:21 신고 수정/삭제 댓글

    제 생각에도 화현님 말씀처럼 linkedlist를 사용한 stack을 구현하여 word splitter의 출력을 때려넣는 문제일듯 싶네요^^;

    • Favicon of http://signpen.net 싸인펜 2007.10.07 01:41 신고 수정/삭제

      이거 난감하네요..ㅠㅠ 도움을 드려볼려고 뚝딱거려 본건데 오히려 잘못된정보로 피해만 가게 생겼습니다....;;

      화현님의 댓글과 루미넌스님의 댓글을 모두 보고 곰곰히 생각해 봤는데 두 분께서 말씀하시는 내용이 맞는것 같아요. 이를 어쩌죠..;;

  5. Favicon of http://smilestory.net/blog 태양의눈물 2007.10.06 22:57 신고 수정/삭제 댓글

    LIFO 아닌감? Last In First Out 후입선출 ㅋㅋㅋ 수정요망 뭐그거나 이거나 마찬가지긴 하지만 그렇고 아무것도 쓰지 않은상태에서 애드센스 신청했다가 짤렸당. ㅋㅋ

    • Favicon of http://signpen.net 싸인펜 2007.10.07 01:46 신고 수정/삭제

      으하하~ 이런 실수가!!
      그냥 머릿속에 떠오르는대로 적었더니 잘못 적었나보네..ㅎㅎ

      애드센스 실패했으면 다음에서도 애드센스처럼 애드클릭스라는 서비스를 하고 있으니까 그 쪽도 한번 알아봐바~ 괜찮은 것 같던데~

댓글 쓰기