스택(STACK)을 이용해서 만든 계산기

 

#include "iostream.h"
#include "iomanip.h"
#include "ctype.h"
#include "string.h"
#include "stdlib.h"

/*
차례로 스택에 5 4 1이란 값을 저장하면
|-------|
|-------|
|-------|
|-------|
|-------|

-> top = -1 스택이 비어있는 상태입니다.

|-------|
|-------|
|-------|
|-------|
| 5 | -> top
|-------|

|-------|
|-------|
|-------|
| 4 | -> top
|-------|
| 5 |
|-------|

|-------|
|-------|
| 1 | -> top
|-------|
| 4 |
|-------|
| 5 |
|-------|

push()소스를 보시면 아시겠지만 stack[++top]
이렇게 해주는것은 초기화가 -1로 되어있기 때문에
stack[0]번지부터 값을 넣어주기 위한 것이지요.
여기서 자료를 꺼내게 (pop)하게 되면 소스와 마찬가지로
stack[top--]입니다.

|-------|
|-------|
|-------|
| 4 | -> top
|-------|
| 5 |
|-------|
1이란 자료를 꺼내고 top은 한칸 아래로 내려가게 됩니다.
마지막 5의 값까지 꺼내게 되면 top 은 -1이 되겠지요.
이것이 스택입니다. 그리고 왜 스택을 이용해 계산기를
만들어야 하냐면요..우선 컴퓨터가 연산을 할때
우리가 5+3*5 라는 산술식을 입력하게 되면
컴퓨터는 연산자를 중심으로 앞뒤의 숫자를 계산하게 됩니다.
그런데 연산자에는 우선순위가 있지요? 그리고 괄호도 있습니다.
그렇기 때문에 우선 산술식을 후위연산자로 바꿔줘야 하는데요
535*+입니다. 바꾸는 법은 이산수학하셨으면 아실꺼예여.
이렇게 후위연산자로 바꾼 식에서 숫자들은 모두 스택에 집어넣구여
연산자가 나오면 스택에서 하나씩 출력하여 계산하면 됩니다.
스택에 5 3 5가 있고 첫번재 *연산자가 나옵니다. 5와 3을 꺼내어 *
을 하고 계산된 결과를 스택에 집어넣으면 5 15가 되겠지요?
그다음 +연산자가 나옵니다. 15와 5 를 꺼내어 계산을 하면 우선순위
에 맞게 계산이 되어집니다. 이 부분을 이해하지 못하신다면 아래
소스도 이해가 안가실 꺼예여. 여러 산술식을 후위연산자로 바꾸고
스택에 집어넣었다가 꺼내면서 계산을 해보세요.

이제 소스설명으로 넘어가겠습니다.

*/

const int StackSize=10;

class CharStack {
private:
int stack[StackSize];
int top;
public:
CharStack() { top = -1; }
void push(char val) { stack[++top] = val; }
char pop() { return stack[top--]; }
int isEmpty() { return top == -1; } // top이 -1이면 스택이 비어있는 것이지요
int isFull() { return top == StackSize-1; } // 이것역시 top이 9의 값을 가지면
//더이상 자료를 넣을수 없습니다.
void init() { top = -1; } // 스택을 초기화 시키는 것입니다.
char getTop() { return stack[top]; } // 현재 스택의 자료를 가져옵니다.
}; //이것이 일반적인 스택의 구조입니다.
//char를 위한 스택

class IntStack {
private:
int stack[StackSize];
int top;
public:
IntStack() { top = -1; }
void push(int val) { stack[++top] = val; }
int pop() { return stack[top--]; }
int isEmpty() { return top == -1; }
int isFull() { return top == StackSize-1; }
}; //위와 같은구조로 정수를 담기위한 스택입니다.

//우선 메인으로 내려가세요

class Calculator {
private:
char buffer[80];
char postfix[80];
IntStack s1;
CharStack s2;
void result();
int priority(char);
public:
void calculate(char[]);
};

int Calculator::priority(char ch)
{
if(ch == '*' || ch == '/')
return 3;
else if(ch == '+' || ch == '-')
return 2;
else
return 1;
}//우선순위에 따라 리턴값을 줍니다.

void Calculator::calculate(char temp[])
{
strcpy(buffer, temp); //전달받은 문자열을 buffer에 복사합니다.

                             //strcpy(복사될 변수의 주소,  복사할 변수의 주소);

int i = 0, j = 0;
char ch;

while (buffer[i] != '\0') { // 문자열이 끝날때까지 실행됩니다.
if (buffer[i] == ' ')
i++; //공백을 제거하고
else if (isdigit(buffer[i])) { //숫자라면
while (isdigit(buffer[i])) //숫자인동안
postfix[j++] = buffer[i++]; //postfix배열에 저장합니다.
postfix[j++] = ' '; //그리고 공백을 넣어 숫자와 숫자사이를 구분합니다.
}
else if (buffer[i] == '(') { //여는 괄호가 나오면 스택에 저장합니다.
s2.push(buffer[i]);
i++;
}
else if (buffer[i] == ')') { //닫는 괄호가 나오면
ch = s2.pop(); //스택에서 pop을 하여
while (ch != '(') { //여는 괄호가 아니라면
postfix[j++] = ch; //postfix에 저장하고
postfix[j++] = ' '; //연산자를 구분하기 위해 공백을 입력합니다.
ch = s2.pop(); //여는 괄호가 나오면 반복문을 빠져나가고
//여는 괄호는 그냥 없어집니다.
//어차피 후위표기식은 괄호가 없기때문에..
}
i++;
}
else { //연산자가 나올경우
if (s2.isEmpty()) //스택이 비어있으면
s2.push(buffer[i++]); //무조건 집어넣고
else { //스택이 비어있지 않은경우
while (!s2.isEmpty() && priority(s2.getTop()) >= priority(buffer[i])) {
//스택이 비어있지 않고 스택의 맨위의 문자가 현재 문자보다 우선순위가 높거나
//같으면 (priority함수로 올라가 봅니다.)
ch = s2.pop();
//스택의 연산자를 pop하여
postfix[j++] = ch; //postfix에 저장합니다.
postfix[j++] = ' '; //그리고 공백을 이용하여 구분
}
s2.push(buffer[i]); //그리고 현재 연산자를 집어넣습니다.
//우선순위에 의해 현재 연산자는 맨 위에 올라가게 하는거지요
i++;
}
}
}
while (!s2.isEmpty()) { //그리고 스택이 비어있지 않은경우
ch = s2.pop(); //남아있는 연산자를 pop하여
postfix[j++] = ch; //postfix배열에 저장하고
postfix[j++] = ' '; //공백을 이용하여 구분합니다.
}
postfix[j] = '\0'; //마지막에 널값을 넣어주어 문자열을 완성합니다.
result(); //여기까지 postfix 후위연산식이 완성되었고, result함수를 호출합니다.
}

void Calculator::result()
{
int i = 0, k;
char token[5];
int num, number, num1, num2;
char ch;

while (postfix[i] != '\0') { //위에서 만들어놓은 후위연산식이 끝날때까지 반복
if (isdigit(postfix[i])) { //숫자라면
k = 0;
while (isdigit(postfix[i])) //숫자인동안
token[k++] = postfix[i++]; //token에 저장합니다.
token[k] = '\0'; //마지막에 널값을 넣어 문자열을 완성하고
num = atoi(token); //atoi를 이용해 정수로 변환하여
s1.push(num); //정수형 스택에 저장합니다.
}
else if (postfix[i] == ' ') //공백을 건너뛰어
i++;
else { //연산자가 나오면
ch = postfix[i++];
num1 = s1.pop(); //우선 스택의 숫자 두개를
num2 = s1.pop(); //pop하고
if (ch == '+') //연산자에 맞는 계산을 하여
number = num2 + num1;
else if (ch == '-')
number = num2 - num1;
else if (ch == '*')
number = num2 * num1;
else if (ch == '/')
number = num2 / num1;
s1.push(number); //다시 계산된 값을 스택에 저장합니다.
}
i++;
}
cout << "result" << setw(10) << ":" << s1.pop() << endl;
} //결과가 나오겠지요?

void main()
{
char temp[80];

cout.setf(ios::left); //출력할때 정렬을 위한 문장입니다.

Calculator myCalc1; //클래스의 객체를 생성하구여

while (cin.getline(temp, 80)) //사용자에게 한줄을 입력받고
myCalc1.calculate(temp); //입력받은 것을 calculate함수에 호출합니다.
} //->calculate함수로 올라가세요

 

//괄호 들어가는 수식와 2+3*5같은
//수식에 우선순위 계산 모두 됩니다.