[c++] Infix expression을 Postfix expression으로 변환하기

문제

 

Infix expression을 Postfix expression으로 변환하는 프로그램을 작성하시오.

---

 

 

문제 포인트 

1) stack class를 구현할 수 있는가

2) stack의 기본 성질(push, pop, top_element 등)을 알고 구현할 수 있는가

3) bool 타입 + 조건문이 들어간 함수를 구현할 수 있는가 

4) infix 와 postfix를 이해하는가 

5) main함수 외 다른 함수를 구현하고 이를 호출하여 사용할 수 있는가 

6) 사용자 지정 우선순위를 만들어 이를 반영하는 함수 조건문을 구현할 수 있는가 

 

 

#include <iostream>
#include <stack>
#define SIZE 100
#define EOS '$'
using namespace std;

class op_stack {
char s[SIZE];
int top;

public:
op_stack();
void push(char x);
char pop();
bool empty();
char top_element();
};
// 초기화
op_stack:: op_stack() {
top = 0 ;
}

void op_stack:: push(char x) {
s[top] = x;
top++;
}

char op_stack::pop() {
top--;
return(s[top]);
}

bool op_stack::empty() {
return(top == 0);
}

char op_stack::top_element(){
return(s[top-1]);
}

// operand인지 아닌지 확인
bool is_operand(char ch){
if(((ch == '(') || (ch == ')')) || (ch == '+') || (ch == '-') ||
(ch == '*') || (ch == '/') || (ch == '%') || (ch == '$'))
return true;
else
return false;
}

// 우선순위 구하는 함수 0>1>2 -> 높을수록 빠름
// 숫자가 높은것부터 팝
int get_precedence(char op) {
if((op == '$') || (op == '(') || (op == ')') ) return (0);
if ((op == '+') || (op == '-')) return (1);
if((op == '*') || (op == '/') || (op == '%')) return(2);

return (-1);
}


// infix -> postfix 함수
string in_to_post(string input) {
string output = "";
op_stack stack1;

stack1.push(EOS);

for(int i=0; i<input.size(); i++) {
char ch = input[i];

// 현재 문자가 문자열인 경우 - output문자열에 추가
if(!is_operand(ch)) {
output = output + ch;
}
// 부호 중 여는 괄호 스택에 넣기
else if(ch == '(') {
stack1.push(ch);
}
// 부호 중 닫는 괄호
// -> 스택이 비어있지않고 탑 요소가 여는 괄호가 아니면 문자열에 추가하기
else if(ch == ')') {
while(!stack1.empty() && stack1.top_element() != '(') {
output = output + stack1.pop();
}
// -> 스택이 비어있지않고 탑 요소가 여는 괄호면 스택1에서 빼기
if (!stack1.empty() && stack1.top_element() == '(') {
//cout << stack1.pop(); //출력 확인용
stack1.pop();
}
}
// 문자열도 아니고 괄호도 아니고 일반 부호일때 - 스택이 비어있지않은 상태에서 우선순위를 확인하고 스택에 추가
else {
while (!stack1.empty() && get_precedence(ch) <= get_precedence(stack1.top_element())){
output = output + stack1.pop();
}
stack1.push(ch);
}
}

// 끝날때까지 출력
while(stack1.top_element()!=EOS){
output += stack1.pop();
}

//cout << output ;
// output 넘겨주기
return output;
}


int main() {

string infix;

cout << "input an infix expression to convert : ";
cin >> infix;

cout << "postfix : " << in_to_post(infix) << endl;

cout << endl;
return 0;

}