스택과 계산기

표기법 변환을 위한 스택의 활용

4.2.2) 표기법 변환을 위한 스택의 활용

식을 중위 표기법에서 후위 표기법으로 변환하는 과정은 다음과 같이 진행된다.

1. 피연산자라면 후위 표기식의 끝에 추가한다.

2. 연산자라면? -> ‘연산자 보관소의 상태를 확인한다.

2.1) ‘연산자 보관소에 저장된 연산자가 없다면 추가한다.

2.2) ‘연산자 보관소에 저장된 연산자가 있다면? -> 연산자의 우선순위를 비교한다.

2.2.1) 보관소에 마지막으로 저장된 연산자가 우선순위가 높다면 새 연산자보다 우선순위가 낮은 보관소의 모든 연산자를 보관소에서 꺼내 후위 표기식의 끝에 추가하고 새 연산자를 보관소에 저장한다.

2.2.2) 새 연산자의 우선순위가 높다면 새 연산자를 보관소에 저장한다.

2.2.3) 두 연산자의 우선순위가 같다면 새 연산자보다 우선순위가 낮은 보관소의 모든 연산자를 보관소에서 꺼내후위 표기식의 끝에 추가하고 새 연산자를 보관소에 저장한다.

3. 1~2 과정을 반복한다.

4. 분석이 끝나면 보관소에 남은 모든 연산자를 후위 표기식에 추가한 후 후위 표기식을 반환하고 종료한다.

이를 위해 스택을 활용할 수 있다.

1. 피연산자라면 후위 표기식’ 배열의 끝에 추가한다.

2. 연산자라면? -> ‘연산자 스택의 상태를 확인한다.

2.2.1) 스택의 최상위 연산자가 우선순위가 높다면 새 연산자보다 우선순위가 낮은 보관소의 모든 연산자를 스택에서 팝 하여 후위 표기식의 끝에 추가하고 새 연산자를 스택에 푸시 한다.

2.2.2) 새 연산자의 우선순위가 높다면 새 연산자를 보관소에 푸시 한다.

2.2.3) 두 연산자의 우선순위가 같다면 새 연산자보다 우선순위가 낮은 보관소의 모든 연산자를 스택에서 팝 하여후위 표기식의 끝에 추가하고 새 연산자를 스택에 푸시 한다.

3. 1~2 과정을 반복한다.

4. 분석이 끝나면 스택에 남은 모든 연산자를 후위 표기식에 추가한 후 후위 표기식을 반환하고 종료한다.

다음은 스택을 활용하여 중위 표기식을 후위 표기식으로 변환하는 예제이다소괄호에 대한 처리는 아직 설명하지 않았으므로 적용하지 않았다.

03_in_to_post.cpp

#include <iostream>

typedef std::string Exception;

// 공용 함수

inline bool is_digit(char ch) { return ('0' <= ch && ch <= '9'); }

// 스택 정의

typedef char Data;

class Stack {

static const int MAX_STACK_SIZ = 256;

Data _list[MAX_STACK_SIZ];

int _count;

private:

inline bool is_full() const { return _count == MAX_STACK_SIZ; }

public:

Stack() : _count(0) {}

void push(const Data &data) {

if (is_full()) throw Exception("Stack is full");

_list[_count++] = data;

}

Data pop() {

if (is_empty()) throw Exception("Stack is empty");

return _list[--_count];

}

Data top() const {

if (is_empty()) throw Exception("Stack is empty");

return _list[_count - 1];

}

inline bool is_empty() const { return _count == 0; }

inline int count() const { return _count; }

};

// 사용할 함수

int op_pri(char ch); // get operator's priority

// convert infix notation expression

// to postfix notation expression

void infix_to_postfix(char *postfix, const char *infix);

int main(void) {

try {

int loop;

std::cin >> loop;

const int MAX_EXPR_LEN = 256;

char infix[MAX_EXPR_LEN] = "";

char postfix[MAX_EXPR_LEN] = "";

while (loop-- > 0) {

std::cout << "Enter expression: ";

std::cin >> infix;

infix_to_postfix(postfix, infix);

std::cout << infix << " : " << postfix << std::endl;

}

return 0;

}

catch (Exception &ex) {

std::cerr << ex.c_str() << std::endl;

return 1;

}

}

// 구현

int op_pri(char ch) { // get operator's priority

int priority = 0;

switch (ch) {

case '+': priority = 1; break;

case '-': priority = 1; break;

case '*': priority = 2; break;

case '/': priority = 2; break;

default: throw Exception("Invalid operator");

}

return priority;

}

void infix_to_postfix(char *postfix, const char *infix) {

// convert infix notation expression

// to postfix notation expression

if (is_digit(*infix) == false)

throw Exception("Invalid infix notation expression");

char ch;

Stack opStack; // operator stack

for (ch = *infix; (ch = *infix) != '\0'; ++infix) {

if (is_digit(ch)) {

while (is_digit(*infix)) {

*postfix++ = *infix++;

}

--infix;

}

else { // is_operator

if (opStack.is_empty() == false) {

// get operator priority

int new_pri = op_pri(ch);

while (opStack.is_empty() == false) {

if (new_pri <= op_pri(opStack.top())) {

*postfix++ = opStack.pop();

}

else {

break;

}

}

}

opStack.push(ch);

}

}

// 스택에 남은 연산자를

while (opStack.is_empty() == false) {

char op = opStack.pop();

*postfix++ = op;

}

*postfix = '\0';

}

 

댓글

댓글 본문
버전 관리
한도영
현재 버전
선택 버전
graphittie 자세히 보기