자료구조 정복하기 with C++ (5)후위표기식 계산기
자료구조 정복하기 with C++ (5)후위표기식 계산기
직접 코딩하면서 자료구조 공부하기
개요
자료구조와 알고리즘은 프로그램을 구성하는 가장 핵심적인 요소입니다. 프로그램 개발을 집을 짓는 것에 비유한다면 흙이나 모래, 시멘트, 목재와 같은 자재들이 바로 ‘자료구조’에 해당되고, 이러한 자재들을 이용해서 집을 짓는 것이 ‘알고리즘’에 해당됩니다. 자료구조는 가장 기본적이고 중요한 부분이기 때문에 복습하는 겸해서 직접 여러가지 자료구조를 코딩하면서 공부하기로 했습니다.
후위표기식 계산기
수식 표기법에는 연산자를 기준으로 전위, 중위, 후위 표기법이 있습니다. 일반적으로 우리가 사용하는 표기법은 중위 표기법이지만 컴퓨터에서는 중위 표기식을 후위 표기식으로 변환하여 계산 합니다. 이 과정에서 앞서 배운 자료구조를 사용할 수 있습니다. 따라서 이번에는 앞서 구현한 List와 String 자료구조를 이용해 후위 표기식 계산기를 구현합니다.
후위표기식 계산 방법
후위 표기식으로 표현된 식은 다음과 같이 계산하면 된다.
- 앞에서부터 읽으며 피연산자는 스택(Stack)에 쌓는다.
- 연산자를 만나면 스택에서 피연산자 2개를 꺼내 연산을 수행하고 다시 스택에 쌓는다.
- 1~2번을 반복한다.
후위표기식 계산기 기능
후위 표기식 계산기으 기능은 다음과 같다.
- 후위 표기식 계산
- 숫자 혹은 연산자 이외의 값 입력시 오류 처리
- 닫는 괄호만 입력시 오류 처리
- 연산자를 두 번 이상 입력시 오류 처리
Calculator
후위 표기식 계산기는 기본적으로 스택 자료구조를 이용하지만 이번에는 앞서 구현한 String 자료구조도 이용할 것이기 때문에 List로 구현합니다. List, String 헤더와 소스파일을 working directory에 올려둡니다.
Calculator.h
계산기의 헤더파일
#pragma once
#include "List.h"
#include "String.h"
class Calculator
{
private:
List<String> tokens;
int errCode; // 발생된 오류코드 값 : 0 -> 오류 없음 , 다른 값 -> 오류 있음
int value; // 계산된 값
String postfix; // 후위표기식 = 최초 공백으로 초기화
int makePostFix(); // postfix로 변경하는 함수 :
int evaluation(); // postfix를 계산하는 함수 :
// 계산된 값을 구함, 오류 없는경우 0, 오류가 있는 경우, 1을 반환
// 계산된 값은 value 에 저장, 오류시 적절한 코드를 errCode 에 저장 (오류코드는 각자가 정의)
public:
Calculator();
int getErrorCode(); // 오류코드 반환
int setExpression(const char* expr); // expr에 전달된 수식(중위표기식)을 postfix로 변경하고 계산하는 함수
// 오류 없는경우, 0, 오류가 있는 경우, 1을 반환
String getPostFix(); // 변환된 후위표기식을 반환 --> 오류가 있을경우 최초값인 공백이 리턴
int getValue(); // 수식 오류있음 --> 예외발생
// 수식 오류없음 --> 결과값 리턴
int isOperator(char c); //연산자 판단 함수
int getOperator(char c); //연산자 판별 함수
int getPriority(char c); //연산자 우선순위 리턴 함수
};
Calculator.cpp
계산기 소스코드
#include "Calculator.h"
#include <iostream>
#include <cctype>
#include <stdlib.h>
using namespace std;
Calculator::Calculator() {
}
int Calculator::getErrorCode() {
return errCode;
}
int Calculator::setExpression(const char* expr) {
char tmp[100];
int tmpCnt = 0;
for (int i = 0; expr[i] != '\0'; i++) {
if (expr[i] == ' ')
continue;
if (isOperator(expr[i])!=0) {
if (tmpCnt != 0) {
String tmpStr(tmp, tmpCnt);
tokens.addItem(tmpStr);
}
tokens.addItem(expr[i]);
tmpCnt = 0;
}
else if (isdigit(expr[i])) {
tmp[tmpCnt++] = expr[i];
}
else {
return 1;
}
}
String tmpStr(tmp, tmpCnt);
tokens.addItem(tmpStr);
makePostFix();
evaluation();
return 0;
}
String Calculator::getPostFix() {
return postfix;
}
int Calculator::getValue() {
return value;
}
int Calculator::makePostFix() {
List<char> tmp;
int bracket = 0;
int duplicate = 0;
String tmpPostfix1;
for (int i = 0; i < tokens.getItemCount(); i++) {
if (isOperator(tokens.getItem(i).toChar()) == 1) {
tmp.addItem(tokens.getItem(i).toChar());
bracket++;
duplicate = 0;
}
else if (isOperator(tokens.getItem(i).toChar()) == 2) {
if (bracket != 0) {
int j;
for (j = tmp.getItemCount() - 1; tmp.getItem(j) != '('; j--) {
String str(tmp.removeAt(j));
tmpPostfix1 = tmpPostfix1.Concat(str);
}
tmp.removeAt(j);
bracket--;
duplicate = 0;
}
else {
return 1;
}
}
else if (isOperator(tokens.getItem(i).toChar()) == 3) {
for (int j = tmp.getItemCount() - 1; j >= 0; j--) {
if (getPriority(tokens.getItem(i).toChar()) <= getPriority(tmp.getItem(j))) {
String str(tmp.removeAt(j));
tmpPostfix1 = tmpPostfix1.Concat(str);
}
else {
tmp.addItem(tokens.getItem(i).toChar());
break;
}
}
if (tmp.getItemCount() == 0) {
tmp.addItem(tokens.getItem(i).toChar());
}
duplicate++;
}
else {
String str(tokens.getItem(i).getString(), tokens.getItem(i).Length());
tmpPostfix1 = tmpPostfix1.Concat(str);
duplicate = 0;
}
if (duplicate > 1) {
errCode = 2;
return 1;
}
}
for (int i = tmp.getItemCount() - 1; i >= 0; i--) {
String str(tmp.removeAt(i));
tmpPostfix1 = tmpPostfix1.Concat(str);
}
postfix = tmpPostfix1;
return 0;
}
int Calculator::evaluation() {
List<int> tmp2;
int j = 0;
for (int i = 0; i < postfix.Length(); i++) {
if (postfix.getChar(i) == ' ') {
continue;
}
if (isdigit(postfix.getChar(i))) {
tmp2.addItem(postfix.getChar(i) - '0');
j++;
}
else if (isOperator(postfix.getChar(i)) != 0) {
if (getOperator(postfix.getChar(i)) == 1) {
int operator1, operator2;
operator1 = tmp2.getItem(j - 2);
operator2 = tmp2.getItem(j - 1);
tmp2.removeAt(j - 1);
tmp2.removeAt(j - 2);
tmp2.addItem(operator1 + operator2);
j -= 1;
}
else if (getOperator(postfix.getChar(i)) == 2) {
int operator1, operator2;
operator1 = tmp2.getItem(j - 2);
operator2 = tmp2.getItem(j - 1);
tmp2.removeAt(j - 1);
tmp2.removeAt(j - 2);
tmp2.addItem(operator1 - operator2);
j -= 1;
}
else if (getOperator(postfix.getChar(i)) == 3) {
int operator1, operator2;
operator1 = tmp2.getItem(j - 2);
operator2 = tmp2.getItem(j - 1);
tmp2.removeAt(j - 1);
tmp2.removeAt(j - 2);
tmp2.addItem(operator1 / operator2);
j -= 1;
}
else if (getOperator(postfix.getChar(i)) == 4) {
int operator1, operator2;
operator1 = tmp2.getItem(j - 2);
operator2 = tmp2.getItem(j - 1);
tmp2.removeAt(j - 1);
tmp2.removeAt(j - 2);
tmp2.addItem(operator1 * operator2);
j -= 1;
}
}
else {
errCode = 1;
return 1; //표기식이 연산자나 숫자가 아님
}
}
value = tmp2.getItem(0);
return 0;
}
int Calculator::isOperator(char c) {
switch (c) {
case '(':
return 1;
case ')':
return 2;
case '+':
case '-':
case '/':
case '*':
return 3;
}
return 0;
}
int Calculator::getPriority(char c) {
switch (c) {
case '(':
return 1;
case '+':
case '-':
return 2;
case '/':
case '*':
return 3;
}
return 0;
}
int Calculator::getOperator(char c) {
switch (c) {
case '+':
return 1;
case '-':
return 2;
case '/':
return 3;
case '*':
return 4;
}
return 0;
}
결과
main.cpp
#include "List.h"
#include "String.h"
#include "Calculator.h"
#include <iostream>
using namespace std;
int main()
{
char expr[1000];
Calculator c;
cout << "수식을 입력하시오: ";
cin.getline(expr, 1000);
if (!c.setExpression(expr))
{
String postfix;
postfix = c.getPostFix();
try {
cout << "후위표기식 : ";
c.getPostFix().print();
cout << " 결과값: " << c.getValue() << endl;
if (c.getErrorCode() == 1) {
throw "표기식에 여는 괄호가 없습니다.";
}
else if (c.getErrorCode() == 2) {
throw "연산자는 한 번만 입력해야합니다.";
}
}
catch (const char* errmsg)
{
cout << errmsg << endl;
}
}
else {
cout << "표기식이 틀렸습니다." << endl;
}
return 0;
}
후위 표기식 계산기를 구현했습니다. 결과가 잘 나옵니다!
(8 / 2 – (3 + 3) * 2 -> 8 2 / 3 - 3 2 * + 의 경우, 결과: -8)
숫자 혹은 연산자 이외의 값 입력(setExpression 오류: return 1)
닫는 괄호만 입력(errCode = 1)
연산자를 두 번 이상 입력(errCode = 2)
