728x90
postfix notation transformation
중위표기식을 후위 표기식으로 변환하는 코드이고 ArrayStack(1)의 헤더 파일을 이용한다.
#include <iostream>
#include "ArrayStack.h"
using namespace std;
//후위표기식 변환 함수
string postfix_transform(ArrayStack<char>& oper_stack, string infix) {
string ans; //결과를 담아둘 ans 문자열 선언
ArrayStack<char> checker_stack;
//음수가 입력된 경우 error 처리
for (const char& check : infix) { //범위기반 반복문 사용
if (check == '-') { //음수일 가능성이 존재하는 -기호 조사
if (checker_stack.empty()) { //-가 문자열의 첫번째 문자인 경우 error 출력
return "ERROR: can't control negative";
}
else if (checker_stack.top() == '-' or checker_stack.top() == '+' or
checker_stack.top() == '*' or checker_stack.top() == '/') {
//-가 연산자 바로 뒤에 출력되는 경우 즉 stack의 top이 연산자인 경우 error 출력
return "ERROR: can't control negative";
}
}
//-가 아닌 경우 stack에 계속 입력
else {
checker_stack.push(check);
}
}
//범위기반 반복문 활용
for (const char& oper : infix) {
//char type의 oper를 상황에 따라 분류
switch (oper) {
case '(': //여는 괄호의 경우
oper_stack.push('('); //일단 stack에 넣음
break;
case ')': //닫는 괄호
while (!oper_stack.empty() and oper_stack.top() != '(') {
//여는 괄호가 나올때까지 stack을 pop
ans.push_back(oper_stack.top()); //문자열끝에 stack의 top을 입력
oper_stack.pop(); //입력한 top은 pop해서 제거
}
oper_stack.pop(); //여는괄호는 stack에 넣지 않고 pop으로 제거
break;
//-------------------*,/,+,-류 연산(1,2,3,4,5번)에서 필요한 연산자)------------------
case '*': case '/': //우선순위가 높은 *과 /의 경우
while (!oper_stack.empty() and (oper_stack.top() == '*' or oper_stack.top() == '/')) {
//*, /을 만난 경우
ans.push_back(oper_stack.top()); //ans문자열에 stack의 top을 입력
oper_stack.pop(); //입력해준 top은 pop
}
oper_stack.push(oper); //자신보다 낮는 우선순위의 연산자를 만나면 stack에 입력
break;
case '+': case '-': //우선순위가 낮은 +와 -의 경우
while (!oper_stack.empty() and oper_stack.top() != '(') {
//top이 여는 괄호가 아닐경우
ans.push_back(oper_stack.top()); //top을 문자열에 입력
oper_stack.pop(); //그후 pop
}
oper_stack.push(oper); //stack의 top에 여는 괄호가 있으면 연산자를 입력
break;
//----------------&&,//,!,<,>류 연산(6,7번)에서 필요한 연산자)-----------------
case '!':
while (!oper_stack.empty() and oper_stack.top() == '!') {
//같은 !를 만난 경우
ans.push_back(oper_stack.top()); //ans문자열에 stack의 top을 입력
oper_stack.pop(); //입력해준 top은 pop
}
oper_stack.push(oper); //자신보다 낮는 우선순위의 연산자를 만나면 stack에 입력
break;
case '&': //우선순위가 높은 &&의 경우
while (!oper_stack.empty() and oper_stack.top() == '!') {
//자신보다 높은 우선순위의 연산자를 만난 경우
ans.push_back(oper_stack.top()); //ans문자열에 stack의 top을 입력
oper_stack.pop(); //입력해준 top은 pop
}
oper_stack.push(oper); //자신보다 낮는 우선순위의 연산자 또는 자신을 만나면 stack에 입력
break;
case '|': //우선순위가 낮은 ||의 경우
while (!oper_stack.empty() and
(oper_stack.top() == '!' or oper_stack.top() == '&')) {
//자신보다 높은 우선순위의 연산자를 만난 경우
ans.push_back(oper_stack.top()); //ans문자열에 stack의 top을 입력
oper_stack.pop(); //입력해준 top은 pop
}
oper_stack.push(oper); //자신보다 낮는 우선순위의 연산자 또는 자신을 만나면 stack에 입력
break;
case '<': case '>': //우선순위가 가장낮은 <와 >의 경우
while (!oper_stack.empty() and oper_stack.top() != '(') {
//top이 여는 괄호가 아닐경우
ans.push_back(oper_stack.top()); //top을 문자열에 입력
oper_stack.pop(); //그후 pop
}
oper_stack.push(oper); //stack의 top에 여는 괄호가 있으면 연산자를 입력
break;
default: //연산자가 아닌 경우
ans.push_back(oper); //문자들은 문자열에 바로 입력
}
}
while (!oper_stack.empty()) { //stack에 값이 존재하는 경우
ans.push_back(oper_stack.top()); //문자열에 top을 입력하고
oper_stack.pop(); //pop해줌
}
return ans; //재구성한 식을 return해줌
}
int main() {
ArrayStack<char> oper_stack;
cout << postfix_transform(oper_stack, "A*B*C") << endl;
cout << postfix_transform(oper_stack, "((A+(B*C))-(D/E))") << endl;
cout << postfix_transform(oper_stack, "-A+B-C+D") << endl;
cout << postfix_transform(oper_stack, "A*-B+C") << endl;
cout << postfix_transform(oper_stack, "(A+B)*D+E/(F+A*D)+C") << endl;
cout << postfix_transform(oper_stack, "A&&B||C||!(E>F)") << endl;
cout << postfix_transform(oper_stack, "!(A&&!((B<C)||(C>D)))||(C<E)") << endl;
cout << endl << "이상훈 12211813" << endl;
return 0;
}
중위표기식을 후위 표기식으로 변환하는 postfix_transform함수에 관한 코드이다. 이 소스코드의 가장 큰 특징은 문자들은 바로 array에 입력하고 연산자들은 각각의 우선순위에 따라 stack에 담거나 stack의 top을 pop해주고 stack에 담아지는 경우로 나눠진다는 것이다. 이는 수업시간에 배운 내용과 강의노트의 내용을 기반으로 작성하였고 소스코드 내의 주석에서 line by line으로 상세하게 설명되어있다. 소스코드의 또다른 특징은 예외처리 이다. Postfix_transform 함수 초반에 for문을 이용하여 음수가 존재하는 식인 경우 예외처리를 통해 error메세지가 출력되도록 하였다. 마지막 특징으로 연산자들의 유형이 존재했다. 1,2,3,4,5번 식들은 +-*/ 과 같은 우리가 평소에 이용하는 연산자들로 구성되어있는 식들이고 6,7번 식들은 && || !와 같은 논리 연산자들로 이루어져 있는 식들이다. 그러나 두 유형 모두 연산자간의 우선순위만 제대로 설정을 해준다면 무리없이 코드를 완성할 수 있다.
728x90
'Quality control (Univ. Study) > Data structure' 카테고리의 다른 글
자료구조론 과제(1) (0) | 2023.02.17 |
---|---|
ArrayStack(2) (0) | 2022.11.19 |
ArrayStack(1) (0) | 2022.11.18 |
자료구조론(5) (1) | 2022.10.06 |
자료구조론(4) (1) | 2022.10.03 |