[C++][자료구조] 스택을 이용한 후위연산

문제 설명

사용자가 후위연산을 입력받는다 ex) 4 9 *

결과가 출력된다 ex) 36

 

OperandStack.h

피연산자를 넣을 스택 class

#pragma once
// 피연산자 스택 클래스

#include <iostream>
#include <string>
using namespace std;
const int MAX_STACK_SIZE = 20;

inline void error(string message) {
	::cout << message << endl;
	exit(1);
}

class OperandStack
{
private:
	double data[MAX_STACK_SIZE];
	int top;

public:
	OperandStack() {
		top = -1;
		data[MAX_STACK_SIZE];
	}
	~OperandStack() {}

	bool isEmpty() {
		if (top == -1)
			return true;
		else
			return false;
	}
	bool isFull() {
		if (top == MAX_STACK_SIZE - 1)
			return true;
		else
			return false;
	}

	void push(double e) {
		if (isFull())
			error("스택 포화 에러");
		else
			data[++top] = e;
	}

	double pop() {
		if (isEmpty())
			error("스택 공백 오류");
		else
			return data[top--];
	}

	double peek() {
		if (isEmpty())
			error("스택 공백 오류");
		else
			return data[top];
	}

	void display() {
		::cout << "스택 요소 개수 = " << top + 1;
		for (int i = 0; i < top + 1; i++)
			::cout << "<" << data[i] << ">";
		::cout << endl;
	}

	int getTop() {
		return top;
	}
};

 

Main.cpp

#include "OperandStack.h"
#include <iostream>
#include <string>
using namespace std;

void calPostfixExpr(string s);

int main()
{
	string postfix;
	cout << "수식 입력(Postfix): ";
	getline(cin, postfix,'\n');

	calPostfixExpr(postfix);
	return 0;
}

void calPostfixExpr(string s)
{
	int size = s.length();
	OperandStack st;

	for (int i = 0; i < size; i++) {
		char c = s.at(i);

		// c가 공백일 때
		if (c == ' ')
			continue;

		// c가 연산자일 때
		else if (c == '+' || c == '-' || c == '*' || c == '/') {
			double val2 = st.pop();
			double val1 = st.pop();

			switch (c) {
			case '+': st.push(val1 + val2); break;
			case '-': st.push(val1 - val2); break;
			case '*': st.push(val1 * val2); break;
			case '/': st.push(val1 / val2); break;
			}
		}

		// c가 피연산자일 때
		else if (c >= '0' && c <= '9') {
			double val = static_cast<double>(c) - 48;
			st.push(val);
		}
	}

	::cout << st.pop();
}

 

실행결과

---

시행착오

 

2 + 3 = 101

// c가 피연산자일 때

double val = static_cast<double>(c);
st.push(val);

처음에 썼던 코드.

 

1. 스택에 push할 때마다 st.display()로 스택을 출력해본 결과,

c=2일 때 스택에 2가 아니라 50이 추가된다는 걸 깨달음

 

2. static_cast<double>(c)를 하면 val에 double 형의 숫자 2가 아니라 2에 해당하는 유니코드(아스키코드) 50이 저장된다

 

3. 숫자를 맞추어 주기 위해 

double val = static_cast<double>(c) - 48;

48을 빼주었다.

 

 

문자열에서 문자 하나씩 불러오기

교재에 있던 코드는 이해하지 못하고 배운 걸 이용하기로

void calcPostfixExpr(FILE* fp = stdin) { 
	char c;
	OperandStack st; 
    
	while ((c = getc(fp)) != '\n') {

이해하지 못한 부분^^

문자열에서 문자를 하나씩 가져오는 방법인 것 같다

 

>> 내 지식수준에서 이용한 방법

getline(cin, postfix);

를 이용해 문자열을 전체 저장

 

int size = s.length()

length()와 for문을 이용해서 문자열 크기만큼 반복

 

char c = s.at(i);

string class 함수를 이용해 문자열에서 문자를 순서대로 하나씩 접근