Skip to main content Link Menu Expand (external link) Document Search Copy Copied
Hepheir

1232. 사칙연산

Code Battle (`23 동계 대학생 S/W 알고리즘 특강 기초학습 문제)

본 게시글은 개인 학습 용도로 작성한 게시글입니다.

(문제 출처: SW Expert Academy)

  • 이진 트리의 post order 순회 문제
  • “No. 9 사칙연산 유효성 검사” 문제와 유사하나, 이번엔 식이 유효한 지를 검사하는 것이 아닌 계산을 하는 것이다. 저번과 마찬가지로 post order 순회를 통해 답을 구한다.
  • 최대 노드의 개수가 $1,000$ 이하라서 재귀적으로 풀이해도 Stack 영역 메모리 사용량이 크지 않을 것이라 생각하였다.
  • 사칙 연산 트리가 완전 이진 트리가 아니기 때문에, 자식 노드의 유무 혹은 그 번호를 예측할 수 없다. 즉, stdin에서 입력 받아 사용해야 한다.
  • 자식 노드 번호가 항상 주어지는 것이 아니어서 std::cin의 >> 연산자로 입력 받기에는 다소 번거로움이 있다. 해결책으로 Java 언어의 BufferedReader + StringTokenizer의 조합과 유사한 동작을 하는 코드를 작성하였다. 이진 트리 문제 보다는 문자열 처리 문제로 기억에 남는 느낌이다.
#include <iostream>

#define MAX_N 1000
#define BUFFER_CAPACITY 32

using namespace std;

int stoi(char *str) {
	int retval = 0;
	int d = 0;
	while (str[d] != '\0') {
		retval *= 10;
		retval += str[d] - '0';
		d++;
	}
	return retval;
}

struct Node {
	char data[BUFFER_CAPACITY];
	Node* left;
	Node* right;

	void setData(char* src) {
		char *dst = data;
		while (*src != '\0') {
			*dst = *src;
			src++;
			dst++;
		}
		*dst = '\0';
	};

	void init() {
		left = nullptr;
		right = nullptr;
		data[0] = '\0';
	}

	double calc() {
		switch (data[0])
		{
			case '+':
				return left->calc() + right->calc();
			case '-':
				return left->calc() - right->calc();
			case '*':
				return left->calc() * right->calc();
			case '/':
				return left->calc() / right->calc();
			default:
				return (double) stoi(data);
		}
	};
};

struct BinaryTree {
	Node nodes[MAX_N+1];
	Node *root;

	void init(int size) {
		root = nodes + 1;
		for (int i = 1; i <= size; i++) {
			nodes[i].init();
		}
	};

	Node *getNode(int at) {
		return nodes + at;
	};
} tree;

struct StringTokenizer {
	char buffer[BUFFER_CAPACITY];
	char *pointer;

	void init() {
		pointer = buffer;
	};

	char *nextToken() {
		char *retval = pointer;
		while (*pointer != ' ' && *pointer != '\0') {
			pointer++;
		}
		*pointer = '\0';
		pointer++;
		return retval;
	};

	bool hasNext() {
		return *pointer != '\0';
	};
} stringTokenizer;

static int solve()
{
	int size;
	Node *node;
	cin >> size;
	cin.ignore();
	tree.init(size);
	for (int i = 0; i < size; i++)
	{
		cin.getline(stringTokenizer.buffer, BUFFER_CAPACITY, '\n');
		stringTokenizer.init();
		node = tree.getNode(stoi(stringTokenizer.nextToken()));
		node->setData(stringTokenizer.nextToken());
		if (stringTokenizer.hasNext()) {
			node->left = tree.getNode(stoi(stringTokenizer.nextToken()));
			node->right = tree.getNode(stoi(stringTokenizer.nextToken()));
		}
	}
	return tree.root->calc();
}

int main(int argc, char **argv)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	for (int test_case = 1; test_case <= 10; ++test_case)
	{
		printf("#%d %.0d\n", test_case, solve());
	}
	return 0;
}

Back to top