자료구조
[자료구조] 후위 수식 계산, 중위 수식을 후위 수식으로 변환하기
minforbackup ・ 2021. 7. 14. 15:55
URL 복사 이웃추가
본문 기타 기능
신고하기
수식이란?
수식이란 연산자와 피연산자로 구성된 문장이다.
연산자에는 산술, 논리, 대입 연산자 등이 있다.
피연산자는 변수 또는 상수이다.
수식의 종류
수식의 표기법은 피연산자에 대한 연산자의 위치에 따라
중위 표기법, 후위 표기법, 전위 표기법으로 나뉜다.
| 표기법 | 수식 |
| 중위 표기법 | a + b * c - d |
| 후위 표기법 | a b c * + d - |
| 전위 표기법 | - + a * b c d |
처음 후위 표기법을 접했을 때 뇌정지가 왔었다. 물론 지금도 중위를 후위로 암산으로 변환하는 것은 어렵지만 한 단계씩 묶다보면 금방 변환할 수 있다. 변환 방법은 아래 링크 참고
![[자료구조] 후위 수식 계산, 중위 수식을 후위 수식으로 변환하기 (2)](https://i0.wp.com/dthumb-phinf.pstatic.net/?src=%22https%3A%2F%2Ft1.daumcdn.net%2Ftistory_admin%2Fstatic%2Fimages%2FopenGraph%2Fopengraph.png%22&type=ff500_300 "[자료구조] 후위 수식 계산, 중위 수식을 후위 수식으로 변환하기 (2)")
중위 표기법과 후위 표기법
| 중위 표기법 | 후위 표기법 |
| 연산자가 피연산자 사이에 온다. | 연산자가 피연산자 다음에 온다. |
| 연산자의 우선 순위가 존재하며, 괄호를 사용하여 우선 순위를 조정할 수 있다. | 연산자의 우선 순위가 없고, 괄호를 사용하지 않는다. |
| 계산 순서가 복잡하다. | 왼쪽에서 오른쪽 방향으로 계산하므로 프로그래밍이 쉽다. |
| 사람이 이해하기는 쉽지만 연산 순서가 복잡하여 프로그래밍이 어렵다. | 사람이 직관적으로 이해하고 작성하기 어렵다. |
구현의 용이성 때문에 프로그램 코드에 포함된 중위 수식은 먼저 후위 수식으로 변환된 후 계산된다.
왜 스택으로 풀어야 하는가?
왜 후위 수식의 계산, 중위 수식을 후위 수식으로 변환하는 문제는 스택으로 풀어야 하는가?
후위 수식을 중위 수식으로 변환하다보면 그 패턴을 찾을 수 있다.
위에서 사용했던 예제를 확인해보자.
후위 수식 : a b c * + d -
중위 수식 : a + b * c - d
위의 후위 수식을 아래 중위 수식으로 바꾸는 과정은 다음과 같다.
a b c * + d -
(((a (b c)* +) d -)
a + b * c - d
(이해가 안된다면 위에 링크 참고!) 연산자는 두 개의 피연산자를 필요로 한다. 따라서 연산자를 만나면 짝이 되는 피연산자 정보가 필요하다. 연산자보다 피연산자를 먼저 만나기 때문에, 연산자를 만나기 전까지 만나는 피연산자들은 별도의 공간에 저장해두어야 한다. 이때 짝이 되는 피연산자들은 연산자를 기준으로 가장 가까이 위치하는 피연산자들이다. 괄호 문자열 문제를 풀 때와 같은 상황이다. 스택에는 이제까지 계산하거나 만난 피연산자들을 저장해두고, top에서만 접근 가능하므로 두 번 pop하면 가장 가까이 위치한 2개의 피연산자들을 얻을 수 있다. 스택이 LIFO 성질을 가진 자료 구조임을 이용한다.
후위 수식 계산
후위 수식 계산 알고리즘
1. 수식을 왼쪽에서 오른쪽으로 스캔한다.
2. 수식에서 들어온 입력이 피연산자이면 스택에 넣는다.
3. 입력이 연산자이면 스택에서 피연산자 2개를 꺼내 계산한 후 결과 값을 다시 스택에 넣는다.
후위 수식의 평가 예시 : 5 7 * 9 + 3 4 / -
| 입력 | 스택 | top | ||
| [0] | [1] | [2] | ||
| 5 | 5 | | | |
| 7 | 5 | 7 | | 1 |
| * | 35 | | | |
| 9 | 35 | 9 | | 1 |
| + | 44 | | | |
| 3 | 44 | 3 | | 1 |
| 4 | 44 | 3 | 4 | 2 |
| / | 44 | | 1 | |
| - | 44 | | | |
후위 수식 57*9+34/-를 계산하는 과정
#define _CRT_SECURE_NO_WARNINGS#include <iostream>#include <string>using namespace std;#define STACK_SIZE 100#define EXPR_SIZE 100 typedef enum {open_b, close_b, plus_op, minus_op, times, divide, mod, eos, operand} priority; // 0, 1, 2, 3, 4, 5, 6, 7, 8class Stack {int data[STACK_SIZE];int top;public:Stack() : top(-1) {}void push(int item) {if (top >= STACK_SIZE - 1) {cout << "stack full\n";return;}data[++top] = item;print_stack();}int pop() {if (top < 0) {cout << "stack empty\n";return -999;}return data[top--];}void print_stack() {for (int i = 0; i <= top; i++) {cout << data[i] << ' ';}cout << '\n';}};class Expr {Stack s;char expr[EXPR_SIZE];int pos = 0;char sym;char sym_type;public:Expr() {}char read_item();int eval_postfix();void set_expr(const char* s) {strcpy(expr, s);}};char Expr::read_item() {sym = expr[pos++];switch (sym) {case '(': sym_type = open_b;break;case ')': sym_type = close_b;break;case '+': sym_type = plus_op;break;case '-': sym_type = minus_op;break;case '*': sym_type = times;break;case '/': sym_type = divide;break;case '%': sym_type = mod;break;case '\0': sym_type = eos;break;default: sym_type = operand;}return sym;}int Expr::eval_postfix() {int op1, op2;sym = read_item();while (sym_type != eos) {if (sym_type == operand) s.push(sym - '0');else {op2 = s.pop();op1 = s.pop();switch (sym_type) {case plus_op: s.push(op1 + op2); break;case minus_op: s.push(op1 - op2); break;case times: s.push(op1 * op2); break;case divide: s.push(op1 / op2); break;case mod: s.push(op1 % op2); break;}}sym = read_item();}return s.pop();}int main() {Stack s;Expr e;const char* tmp = "57*9+34/-";e.set_expr(tmp);e.eval_postfix();return 0;}
스택 클래스와 수식 클래스를 구현하여 사용하였다. 스택 클래스는 앞에서 이미 구현 설명을 마쳤으므로, 이 문제를 해결하기 위해 정의한 수식 클래스에 대한 설명만 간략하게 한다. Expr 클래스의 멤버는 스택, 수식 문자열, 문자열에서 현재 탐색 중인 인덱스를 나타내는 pos, 현재 탐색 중인 문자 sym, 현재 탐색 중인 문자의 타입을 나타내는 sym_type으로 구성된다. sym_type은 위에서 열거형 상수로 선언하였다. 순서대로 여는 괄호, 닫는 괄호, 덧셈, 뺄셈, 곱셈, 나눗셈, 나머지, null, 피연산자의 타입을 나타낸다. 이를 열거형 상수로 나타내는 이유는 수식 클래스에서 지원하는 스택이 정수형을 담을 수 있는 배열이기 때문이다. 위에서 표로 작성한 것처럼 정수와 문자(*, +, ..)를 같은 배열 안에 넣을 수는 없다. 따라서 문자를 나타내는 정수를 매핑하여 저장할 수 있게 했다. 프로그램 내에서는 상수에 별칭을 주었으므로, 문자와 매핑되는 정수는 프로그래머가 신경쓰지 않아도 된다.
수식 클래스의 멤버 함수인 read_item, eval_postfix, set_expr를 살펴보자. set_expr는 문자열 expr의 setter 함수이다. 문자열 상수를 전달받아 expr 멤버에 복사한다. read_item은 expr의 각 문자에 대한 정보를 얻기 위해 사용한다. 이 함수를 호출하면 현재 탐색 중인 문자와 해당 문자의 타입을 알 수 있다. read_item은 eval_postfix에서 expr의 요소를 하나씩 검사하는 반복문에서 사용된다. eval_postfix는 앞에서 살펴본 후위 수식 계산 알고리즘을 구현한 함수이다. (다른 함수는 이 함수를 구현하기 위한 보조 함수이다) expr의 요소를 하나씩 읽고, 해당 문자의 타입에 따라 다른 연산을 실행한다. 피연산자이면 바로 스택에 push, 연산자이면 피연산자를 두개 pop하여 알맞은 계산을 한 뒤 스택에 다시 push. 최종적으로 스택에 남은 계산 결과를 pop한다.
중위 수식을 후위 수식으로 변환
중위 수식을 후위 수식으로 변환하는 과정은 후위 수식 계산 과정보다 조금 더 복잡하다. 우선 중위 수식과 후위 수식의 가장 큰 차이점은 연산자 우선 순위의 유무였다. 중위 수식은 우선 순위가 존재하고 괄호를 사용한다. 반면 후위 수식은 우선 순위가 존재하지 않고 괄호를 사용하지 않는다. 따라서 변환할 때 각 연산자를 우선 순위에 따라 재배열해야 한다. 각 연산자가 변환 수식에서 정확한 위치를 찾을 때까지 스택에 임시로 저장해야 한다. 또한 우선 순위를 조정할 수 있는 괄호 역시 연산자로 취급하여 처리해야 한다.
중위 -> 후위 변환 알고리즘
1.입력이 피연산자 : 바로 출력
2. 입력 연산자 우선순위 > top 우선 순위이거나 스택이 비어있으면 : push 입력
3. 입력 연산자 우선순위 <= top 우선 순위 : pop, push 입력
4. 입력이 '(' : ')'이 들어올 때까지 연산자를 2, 3 규칙에 따라 push
5. 입력이 ')' ; '('이 나올 때까지 스택에서 계속 연산자 pop하고 출력, '('은 출력하지 않음
6. 입력이 eos(null) : 스택의 모든 연산자를 pop하여 출력
| 입력 | 출력 | 스택 | 적용 알고리즘 |
| a | a | 1 | |
| + | a | + | 2 |
| ( | a | + ( | 4 |
| b | a b | + ( | 2 |
| * | a b | + ( * | 2 |
| c | a b c | + ( * | 1 |
| + | a b c * | + ( + | 3 |
| d | a b c * d | + ( + | 1 |
| ) | a b c * d + | + | 5 |
| * | a b c * d + | + * | 2 |
| e | a b c * d + e | + * | 1 |
| '\0' | a b c * d + e * + | 6 |
이 문제에서 스택은 연산자들이 올바른 위치를 찾을 때까지 연산자를 저장해두는 임시 저장 공간이다.
#define _CRT_SECURE_NO_WARNINGS#include <iostream>#include <string>using namespace std;#define STACK_SIZE 100#define EXPR_SIZE 100 class Stack {char data[STACK_SIZE];char top;public:Stack() : top(-1) {}void push(int item) {if (top >= STACK_SIZE - 1) {cout << "stack full\n";return;}data[++top] = item;}char pop() {if (top < 0) {cout << "stack empty\n";return ' ';}return data[top--];}int get_top() {return top;}char get_top_item() {return data[top];}};class PostExpr {Stack s;char expr[EXPR_SIZE];int pos;char token;public:PostExpr() : pos(0) {}int precedence(char op);void infix_to_postfix();void set_expr(const char* s) {strcpy(expr, s);}};int PostExpr::precedence(char op) {switch (op) {case '(': return 0;case '+': case '-': return 1;case '*': case '/': case '%': return 2;}}void PostExpr::infix_to_postfix() {while ((token = expr[pos++]) != '\0') {// 1번 : 피연산자 if (isalnum(token)) cout << token << ' ';// 4번 : (else if (token == '(') s.push(token);// 5번 : ) else if (token == ')') {char tmp;while ((tmp = s.pop()) != '(') cout << tmp << ' ';}// 2, 3번 else {// 3번while (precedence(s.get_top_item()) >= precedence(token) && s.get_top() != -1) {cout << s.pop() << ' ';}// 2, 3번s.push(token);}}// 6번 : eoswhile (s.get_top() != -1) {cout << s.pop() << ' ';}cout << '\n';}int main() {PostExpr e;const char* tmp = "5*7+(4-3)/6%9";e.set_expr(tmp);e.infix_to_postfix();return 0;}
스택은 연산자만을 저장하므로 char형 배열을 사용한다.
후위 표기 수식을 나타내는 PostExpr 클래스를 살펴보자. (포스팅 작성하면서 깨달은 것이지만 후위 표기라기 보다는 그냥 수식 표기를 나타내는 클래스 이름이 더 적합할 듯) 멤버로 스택, 문자열, 현재 탐색 위치를 나타내는 pos, 현재 탐색하고 있는 문자 char를 멤버로 가진다. 멤버 함수로는 expr의 setter, 연산자의 우선 순위를 반환하는 precedence, 중위 표기를 후위 표기로 바꾸는 infix_to_postfix가 있다.
메인 계산을 실행하는 infix_to_postfix는 아까 짰던 알고리즘을 구현하는 함수이다. 탐색 문자가 null이 아닐 때까지 모든 문자 요소에 대하여 검사를 진행한다. 특히 2, 3번 알고리즘을 구현한 반복문을 잘 살펴보자. 2, 3번은 공통적으로 입력된 연산자와 top의 연산자 우선 순위를 비교하고, 입력을 스택에 넣는다. 2, 3번의 차이는 비교 결과에 따른 추가 연산에 있다. 비교 결과가 거짓인 경우 2번에 해당하므로 해당 반복문에 들어가지 않고 push만 하고 끝난다. 비교 결과가 참인 경우 스택에서 pop해야 한다. 이 코드에서는 while로 조건을 판별했으나 if를 사용해도 상관 없다.
인쇄
![[자료구조] 후위 수식 계산, 중위 수식을 후위 수식으로 변환하기 (2024)](data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABCAQAAAC1HAwCAAAAC0lEQVR42mP8/h8AAvMB+NzmkbcAAAAASUVORK5CYII=)