스택 계산기

중위표기식의 식을 입력 받아서 후위 표기식으로 바꾼 후

계산하는 스택 계산기입니다.

후위로 바꾸는 방법을 모르신다면 아래의 글을 참고해주세요

http://donggod.tistory.com/45

그리고 정석적인 방법이 아닙니다!!!

그냥 제가 생각나는데로 코딩했기 때문입니다...ㅠ_ㅠ....(근데 이게 정석일수도? 냐하하..)

문자열로 받은 식을

후위로 바꿉니다.

후위로 바꿀 때 숫자 뒤에는 항상 '$'을 붙였습니다. 문자열이기 때문에 숫자라는 구분을 넣어준 것입니다.

예를들어 1000 + 300

이면

1000300+가 될텐데 1000300인건지 아니면 1000 300 인것인지 구분하기 위함입니다.

그래서 1000$300$+가 됩니다.

후위를 스택으로 계산하는 방법은

후위식에서 AB+C+라는 식이 있으면

A와 B를 스택에 삽입하고 기호를 만나면 스택에서 가장 위의 값 두개를 팝하고 +연산을 한 후에

다시 스택에 넣습니다.

과정을 보여드리자면

스택 : A,B

기호 : +

그럼 A와 B를 꺼내서 (A+B)라는 값이 만들어집니다

이것을 다시 스택에 넣습니다.

스택 : (A+B)

기호 : 

또 스택에 C가들어오겠죠

스택 : (A+B),C

기호 : +

또 두개를 꺼내서 계산합니다

(A+B+C)라는 값이 만들어지곘죠

스택 : A+B+C

기호 :

완성됐습니다!

아래는 코드입니다.

궁금한 점은 댓글 주세요

#include <cstdio>
#include <iostream>
#include <utility>
#include <stack>
#include <string.h>
using namespace std;
 
 
//이전 자료구조 글을 참고하세요 [1918] 후위표기식
// http://donggod.tistory.com/45
//그 코드에서 바뀐 부분만 주석 달겠습니다.
void prefix(char *str, char *output) {
    stack<char> s;
    int oIdx = 0;
 
    for (int i = 0; i < strlen(str); i++) {
        //A~Z가 아닌 숫자로 바뀜
        //숫자일 때 까지 output에 넣고
        //마지막에 '$'를 삽입
        //ex) 1000+30 이면 1000$30$+
 
        if (str[i] >= '0' && str[i] <= '9') {
            int j;
            for (j = i; str[j] >= '0' && str[j] <= '9'; j++) {
                output[oIdx++] = str[j];
            }
            output[oIdx++] = '$';
            i = j - 1;
        }
        else {
            if (str[i] == '(') s.push(str[i]);
            else if (str[i] == ')') {
                while (s.top() != '(') {
                    output[oIdx++] = s.top();
                    s.pop();
                }
                s.pop();
            }
            else if (str[i] == '*' || str[i] == '/') {
                while (!s.empty() && (s.top() == '*' || s.top() == '/')) {
                    output[oIdx++] = s.top();
                    s.pop();
                }
                s.push(str[i]);
            }
            else {
                while (!s.empty() && s.top() != '(') {
                    output[oIdx++] = s.top();
                    s.pop();
                }
                s.push(str[i]);
 
            }
        }
    }
 
    while (!s.empty()) {
        output[oIdx++] = s.top();
        s.pop();
    }
    output[oIdx] = '\0';
}
 
//prefix로 바뀐 output, 인덱스를 포인터로 받음
//'$'를 만날 때 까지 10씩 곱해주며 숫자로 바꾼 후 리턴
int toInt(char *output, int* idx) {
    int ret = 0;
    for (; output[*idx] != '$'; (*idx)++) {
        ret *= 10;
        ret += output[*idx] - '0';
    }
    return ret;
}
 
int calcuration(char *output) {
    stack<int> s;
 
    for (int i = 0; i < strlen(output); i++) {
        if (output[i] >= '0' && output[i] <= '9') {
            int a = toInt(output, &i);//문자열을 숫자로 바꿈
            s.push(a);//스택에 삽입
        }
        else {
            int b = s.top();
            s.pop();
            int a = s.top();
            s.pop();
 
            switch (output[i]) {
            case '+':
                a += b;
                break;
            case '-':
                a -= b;
                break;
            case '/':
                a /= b;
                break;
            case '*':
                a *= b;
                break;
            }
            
            s.push(a);
        }
    }
 
    return s.top();
}
 
int main() {
    char str[10000];
    char output[10000];
 
    scanf("%s", str);
    prefix(str, output);
 
    printf("%d\n", calcuration(output));
 
    return 0;
}