[자바 알고리즘 문제풀이 입문] ch05. Stack, Queue(자료구조) : 4. 후위식 연산(postfix)

 

 

5.4. 후위식 연산(postfix)

 

문제 

후위연산식이 주어지면 연산한 결과를 출력하라

 

입력

352+*9-

 

출력

12

 

---

 

풀이

후위식(postfix)이란?

- 피연산자를 먼저 표시하고 연산자를 나중에 표시하는 방법

- 컴파일러가 사용하는 것으로 스택을 사용하는 예들 중 가장 빈번하게 등장

- ex) 3*(5+2)-9를 후위연산식으로 표현하면 → 352+*9- 로 표현되며 결과는 12이다. 

 

첫 번째 풀이

public int solution(String str) {
    int answer = 0;
    Stack<Integer> stack = new Stack<>();

    // 0 : 48 ~ 9 : 57
    for (char x : str.toCharArray()) {
        if ((int) x >= 48 && (int) x <= 57)
            stack.push(Character.getNumericValue(x));
        else {
            int b = stack.pop();
            int a = stack.pop();
            int result = 0;
            switch (x) {
                case '+':
                    result = a + b;
                    break;

                case '-':
                    result = a - b;
                    break;

                case '*':
                    result = a * b;
                    break;

                case '/':
                    result = a / b;
                    break;

                default:
                    break;
            }
            stack.push(result);
        }
    }
    answer = stack.pop();
    return answer;
}

 

char로 현재 문자가 숫자인지 기호인지 판단하기 위해서 아스키코드 값을 사용하였다. 

정수 0 ~ 9는 아스키코드로 48 ~ 57로 나타낼 수 있다. 

 

char 자료형 앞에 (int)를 붙여주면 정수형으로 캐스팅된다.  

(하지만 자동 형변환이나 강제 형변환으로 문자 '0'이라면 그에 대한 아스키코드인 48이 출력된다.)

 

1. 현재 문자가 숫자이면 stack에 push()한다. 

2. 문자이면 stack에서 두 개를 pop() 한다. (빼기 할 때 큰 수에서 작은 수를 빼줘야 해서 첫 번째로 pop()해준 값을 b로 설정)

3. 문자에 맞는 연산을 해주고 결과를 stack에 push()

4. 후위식 연산이 종료되면 stack의 가장 최근 값을 return 

 

1번에서 getNumericValue()를 사용해 스택에 정수로 바꿔줘서 넣었다.

위에는 아스키코드로 비교하고, 넣을 땐 getNumericValue() 메서드를 썼는데,

int 타입으로 캐스팅하는 부분을 통일해 줬으면 더 좋았을 것 같다.

 

 

두 번째 풀이

강의를 보고 다시 풀어보았다. 

 

차이점은 현재 문자가 숫자인지 체크할 때 나는 아스키코드 값을 사용해서 비교해 줬는데

Character.isDigit() 메서드를 사용함!!! 

이런 메서드도 있구나 알게 되었다. 

 

강의에서는 연산자가 나왔을 때 if, else if를 사용해서 조건문을 처리해 줬는데 

그냥 switch-case문으로 그대로 함

public int solution(String str) {
    int answer = 0;
    Stack<Integer> stack = new Stack<>();

    // 0 : 48 ~ 9 : 57
    for (char x : str.toCharArray()) {
        // if ((int) x >= 48 && (int) x <= 57)
        if (Character.isDigit(x)) // 숫자인지 확인하는 메소드
            stack.push(Character.getNumericValue(x)); // x - 48
        else {
            int b = stack.pop();
            int a = stack.pop();
            int result = 0;
            switch (x) {
                case '+':
                    result = a + b;
                    break;
                case '-':
                    result = a - b;
                    break;

                case '*':
                    result = a * b;
                    break;

                case '/':
                    result = a / b;
                    break;

                default:
                    break;
            }
            stack.push(result);
        }
    }
    answer = stack.pop();
    return answer;
}

 

---

 

메모

❗️char -> int 타입으로 변환하는 방법

아스키코드가 아닌 char 타입의 숫자를 정수 타입의 int로 변환하는 방법은

 

1. '0' 빼주기 (ASCII code 사용)

char c = '1';
int n = c - '0';

아스키코드 표를 살펴보면 문자 0 ~ 9는 10진수 48 ~ 57로 되어있다. (글 하단 아스키코드 표 참고)

따라서 문자 '1'의 아스키코드에서 문자 '0'의 아스키코드를 빼주면 원하는 숫자 1을 얻을 수 있다. 

위의 예시 '1' - '0'은 49 - 48 인 것

 

2. Character.getNumericValue() 메서드 사용

char c = '1';
int n = Character.getNumericValue(c); // 1

Character의 getNumericValue() 메서드를 사용하여 변환할 수 있다. 

 

• ASCII code

       아스키코드 중 제어 문자와 확장 아스키코드를 제외한 부호(영문 자판에 사용되는 부호)를 정리한 것

10진수	부호	10진수	부호	10진수	부호	10진수	부호
032	[3]	056	8	080	P	104	h
033	!	057	9	081	Q	105	i
034	"	058	:	082	R	106	j
035	#	059	;	083	S	107	k
036	$	060	<	084	T	108	l
037	%	061	=	085	U	109	m
038	&	062	>	086	V	110	n
039	'	063	?	087	W	111	o
040	(	064	@	088	X	112	p
041	)	065	A	089	Y	113	q
042	*	066	B	090	Z	114	r
043	+	067	C	091	[	115	s
044	,	068	D	092	\	116	t
045	-	069	E	093	]	117	u
046	.	070	F	094	^	118	v
047	/	071	G	095	_	119	w
048	0	072	H	096	`	120	x
049	1	073	I	097	a	121	y
050	2	074	J	098	b	122	z
051	3	075	K	099	c	123	{
052	4	076	L	100	d	124	|
053	5	077	M	101	e	125	}
054	6	078	N	102	f	126	~
055	7	079	O	103	g

출처 : 나무위키

 

 

• Character.isDigit() : 숫자인지 확인
• Character.isLetter(), Character.isAlphabetic(): 글자인지 확인
• Character.isUpperCase() : 대문자인지 확인
• Character.isLowerCase() : 소문자인지 확인