위 예시에서 후위 표기법에서 나누기(/) 연산자가 더하기(+) 연산자보다 앞에 있으므로 나누기 연산부터 진행 후 더하기 연산을 한다는 것을 알 수 있음
연산자의 우선순위에 대해 알 필요가 없음 - 연산자의 배치 순서에 따라 연산 순서가 결정됨 - 위 같은 특성 때문에 소괄호에 대한 처리도 불필요함
소괄호가 없는 중위표기법에서 후위 표기법으로 변경하는 방법
예시) 중위표현식 : 5+2/7
숫자는 그대로 표현한다.
연산자는 스택에 저장한다.
스택에 연산자가 있을 경우 우선순위를 비교한다. 3-1. 새로 추가할 연산자의 우선순위가 더 높을 경우 스택에 저장한다. 3-2. 새로 추가할 연산자의 우선순위가 더 낮거나 같을경우 스택에 있는 우선순위가 높은 연산자를 빼서 표현하고, 새로운 연산자는 스택에 저장한다.
위 방법을 반복하며 더 이상 남은 중위 표현식이 없을 경우 스택에 저장된 연산자들을 모두 빼서 표현한다.
중위 표현식
후위 표현식
스택
번호
5+2/7
+2/7
5
방법 1
2/7
5
+
방법 2
/7
52
+
방법 1
7
52
/ +
방법 3-1
527
/ +
방법 1
527/+
방법 4
소괄호가 있는 중위 표현식을 후위 표현식으로 변경하는 방법
( ) 연산자는 우선순위가 다른 연산자들 보다 낮다고 가정 - 어디까지 괄호로 묶여 있는 것인지 판단하기 위해 필요
( 연산자 내부의 수직은 ) 연산자를 만날때까지 기존 후위 표기법과 방식이 동일
) 연산자가 나오면 스택에 저장된 모든 연산자를 표현 - ( ) 연산자는 표현하지 않음
1번부터 반복
예시) 중위 표현식 : (1+2*3)/4
중위 표현식
후위 표현식
스택
(1+2*3)/4
1+2*3)/4
(
+2*3)/4
1
(
2*3)/4
1
+ (
*3)/4
12
+ (
3)/4
12
* + (
)/4
123
* + (
/4
123
) * + (
/4
123*+
4
123*+
/
123*+4
/
123*+4/
소괄호가 있는 중위표기법을 후위 표기법으로 변경하는 기능 구현
기존에 직접 구현한 LinkedListStack을 이용 (java 내부에서 사용하는 Stack 사용해도 무방)
연산자 우선순위를 반환하는 메소드 작성
// 연산자 우선순위 반환
public static int getOpPriority(char c){
switch (c) {
case '*':
case '/':
return 3;
case '+':
case '-':
return 2;
case '(':
return 1;
default:
return -1;
}
}
연산자 우선순위를 비교하는 메소드 작성
// 연산자 우선순위 비교
public static int compareOp(char stackOp, char curOp){
int stackOpPriority = getOpPriority(stackOp);
int curOpPriority = getOpPriority(curOp);
// 현재 우선순위가 더 높은 경우
if (stackOpPriority < curOpPriority){
return 1;
}
// 우선순위가 같은 경우
else if (stackOpPriority == curOpPriority){
return 0;
}
// 스택의 우선순위가 더 높은 경우
else {
return -1;
}
}
후위 표기법으로 변경하는 메소드 작성
public static String convPostfix(String infix){
char c = ' ';
Stack opStack = new LinkedListStack();
StringBuilder sb = new StringBuilder();
for(int i=0; i<infix.length(); i++){
c = infix.charAt(i);
// 숫자이면 표현
if (Character.isDigit(c)){
sb.append(c);
}
// 연산자 스택이 비어있을 경우 값 push
else if (opStack.isEmpty()){
opStack.push(c);
}
// 숫자가 아니고 연산자 스택이 비어있지 않은 경우 (연산자가 하나라도 스택에 추가된 경우)
else {
// 여는 괄호가 나오면 스택에 저장 후 다음 문자로
if (c == '('){
opStack.push(c);
continue;
}
// 닫는 괄호가 나올 경우
// 스택에 저장된 모든 연산자를 반환
else if (c == ')'){
char check = ' ';
while(true) {
check = (char) opStack.pop();
if (check == '(') {
break;
}
else {
sb.append(check);
}
}
continue;
}
// 현재 연산자의 우선순위가 더 높은 경우
// 스택에 연산자 저장
if (compareOp((char)opStack.peek(), c) > 0){
opStack.push(c);
}
// 현재 연산자의 우선순위가 더 낮거나 같은 경우
// 스택에 있는 우선순위가 높은 연산자를 빼서 표현
else {
while(!opStack.isEmpty()){
if (compareOp((char)opStack.peek(), c) <= 0){
sb.append(opStack.pop());
}
else {
break;
}
}
opStack.push(c);
}
}
}
char check = ' ';
while(!opStack.isEmpty()) {
check = (char) opStack.pop();
if (check != '(') {
sb.append(check);
}
}
return sb.toString();
}
후위 표기법 계산
public static double postfixCalculate(String postfix){
Stack stack = new LinkedListStack();
char c = ' ';
double op1 = 0;
double op2 = 0;
for(int i=0; i<postfix.length(); i++){
c = postfix.charAt(i);
// 숫자인 경우 스택에 저장
if (Character.isDigit(c)){
stack.push(c);
}
// 연산자인 경우 계산 후 스택에 저장
else {
op2 = Double.valueOf(stack.pop().toString());
op1 = Double.valueOf(stack.pop().toString());
switch (c){
// op2에 먼저 pop한 이유는 후위 표기법으로 변환할 때 순서가 바뀌기 때문
// ex) 3+2 => 스택에 저장 시 3, 2 순으로 저장되는데 스택은 마지막에 push한
// 데이터가 가장 위에 있으므로
case '+':
stack.push(op1 + op2);
break;
case '-':
stack.push(op1 - op2);
break;
case '*':
stack.push(op1 * op2);
break;
case '/':
stack.push(op1 / op2);
break;
}
}
}
return Double.valueOf(stack.pop().toString());
}
전체 소스코드
package Stack;
import Stack.Stack;
import Stack.LinkedList.LinkedListStack;
public class PostfixNotation {
public static void main(String[] args) {
String infix = "(1+2*3)/4";
String postfix = convPostfix(infix);
System.out.println(postfix);
System.out.println(postfixCalculate(postfix));
}
public static double postfixCalculate(String postfix){
Stack stack = new LinkedListStack();
char c = ' ';
double op1 = 0;
double op2 = 0;
for(int i=0; i<postfix.length(); i++){
c = postfix.charAt(i);
// 숫자인 경우 스택에 저장
if (Character.isDigit(c)){
stack.push(c);
}
// 연산자인 경우 계산 후 스택에 저장
else {
op2 = Double.valueOf(stack.pop().toString());
op1 = Double.valueOf(stack.pop().toString());
switch (c){
// op2에 먼저 pop한 이유는 후위 표기법으로 변환할 때 순서가 바뀌기 때문
// ex) 3+2 => 스택에 저장 시 3, 2 순으로 저장되는데 스택은 마지막에 push한
// 데이터가 가장 위에 있으므로
case '+':
stack.push(op1 + op2);
break;
case '-':
stack.push(op1 - op2);
break;
case '*':
stack.push(op1 * op2);
break;
case '/':
stack.push(op1 / op2);
break;
}
}
}
return Double.valueOf(stack.pop().toString());
}
public static String convPostfix(String infix){
char c = ' ';
Stack opStack = new LinkedListStack();
StringBuilder sb = new StringBuilder();
for(int i=0; i<infix.length(); i++){
c = infix.charAt(i);
// 숫자이면 표현
if (Character.isDigit(c)){
sb.append(c);
}
// 연산자 스택이 비어있을 경우 값 push
else if (opStack.isEmpty()){
opStack.push(c);
}
// 숫자가 아니고 연산자 스택이 비어있지 않은 경우 (연산자가 하나라도 스택에 추가된 경우)
else {
// 여는 괄호가 나오면 스택에 저장 후 다음 문자로
if (c == '('){
opStack.push(c);
continue;
}
// 닫는 괄호가 나올 경우
// 스택에 저장된 모든 연산자를 반환
else if (c == ')'){
char check = ' ';
while(true) {
check = (char) opStack.pop();
if (check == '(') {
break;
}
else {
sb.append(check);
}
}
continue;
}
// 현재 연산자의 우선순위가 더 높은 경우
// 스택에 연산자 저장
if (compareOp((char)opStack.peek(), c) > 0){
opStack.push(c);
}
// 현재 연산자의 우선순위가 더 낮거나 같은 경우
// 스택에 있는 우선순위가 높은 연산자를 빼서 표현
else {
while(!opStack.isEmpty()){
if (compareOp((char)opStack.peek(), c) <= 0){
sb.append(opStack.pop());
}
else {
break;
}
}
opStack.push(c);
}
}
}
char check = ' ';
while(!opStack.isEmpty()) {
check = (char) opStack.pop();
if (check != '(') {
sb.append(check);
}
}
return sb.toString();
}
// 연산자 우선순위 반환
public static int getOpPriority(char c){
switch (c) {
case '*':
case '/':
return 3;
case '+':
case '-':
return 2;
case '(':
return 1;
default:
return -1;
}
}
// 연산자 우선순위 비교
public static int compareOp(char stackOp, char curOp){
int stackOpPriority = getOpPriority(stackOp);
int curOpPriority = getOpPriority(curOp);
// 현재 우선순위가 더 높은 경우
if (stackOpPriority < curOpPriority){
return 1;
}
// 우선순위가 같은 경우
else if (stackOpPriority == curOpPriority){
return 0;
}
// 스택의 우선순위가 더 높은 경우
else {
return -1;
}
}
}
결과 전위 표기법 : (1+2*3)/4
전위 표기법 : ((4+2)/4)-(3+2/(7*5))
2자리 이상의 숫자를 연산하려면 List와 StringBuilder로 구현 가능 StringBuilder를 이용해 문자가 나올 때까지 반복하고, 연산자가 나올 경우 숫자를 리스트에 저장하는 방식으로 구현 가능
자료구조가 무엇인지 위키백과를 확인해보면 자료구조는 효율적인 접근 및 수정을 가능하게 하는 자료의 조직, 관리, 저장을 의미한다고 나와있다. 즉, 당연한 말이지만 위의 말 그대로 자료를 어떻게 구성(조직)할 것이고 어떤 방식으로 관리하고 저장할 것인지를 말한다.
자료구조는 알고리즘과 밀접한 관계를 맺고 있는데, 한가지 간단한 예를 들어보면 다음과 같다.
[예시] 반짝이가 일하는 편의점에 홈런볼 5박스가 들어왔는데 박스마다 유통기한이 다르게 들어왔으며 쌓여있는 순서도 유통기한 순서에 맞게 쌓여있는 것이 아니라 뒤죽박죽 섞인채로 쌓여있었다. 반짝이는 홈런볼 재고관리를 쉽게하기 위해 유통기한이 가장 길게 남아있는 박스를 아래에 쌓고 위로 쌓을수록 유통기한이 짧게 남은 박스를 올려두었고, 맨 위에 유통기한이 가장 짧게 남은 박스의 홈런볼부터 차례대로 매대에 진열해 놓았다. 진열된 홈런볼들이 다 팔릴때마다 한박스씩 맨 위에 쌓여있는 박스를 바닥으로 내려 홈런볼들을 꺼낸 후 진열하였다.
위 예시에서 홈런볼은 "자료"를 의미한다. 그리고 이 홈런볼들을 모아놓은 박스를 "조직"이라고 할 수 있다. 즉, 관련있는 것들(홈런볼)을 어떤 방식으로 구성(박스)할 것인지를 말한다. 그리고 유통기한 순서대로 홈런볼을 판매하는데 이것을 "관리"라고 할 수 있다. 이 박스들을 유통기한 순서대로 가장 길게 남은 박스는 아래에 두고 위로는 유통기한이 짧은 박스를 쌓아두는데 이 쌓아두는 것을 "저장"이라고 할 수 있다. 마지막으로 맨 위에 쌓여있는 박스를 바닥으로 내려 홈런볼을 꺼내는 행위를 "알고리즘"이라고 할 수 있다.
나중에 배우게 될 자료구조이지만 위 저장방식은 LIFO(Last-In First-Out)로 나중에 들어간 데이터가 먼저 나오는 자료구조인 스택을 이용하였으며, 알고리즘은 이 자료구조를 이용하여 어떻게 문제를 해결하는지를 말한다. 즉, 자료구조가 결졍되어야 그에 맞는 알고리즘을 결정할 수 있기 때문에 자료구조와 알고리즘은 밀접한 관계를 맺고 있다고 볼 수 있다. 물론 자료구조가 달라지면 알고리즘도 바뀌어야 한다. 위 예시에서 스택 자료구조가 아닌 큐(Queue) 자료구조가 쓰인다면 그에 맞는 알고리즘(맨 위의 상자를 아래로 내린 후 홈런볼을 꺼내는 행위)도 바뀌어야 한다는 뜻이다.
