컴굥일지
[BOJ/백준 1935][C++] 후위 표기식2 본문
문제
https://gyong0117.tistory.com/
문제 내용
후위 표기식과 피연산자들에 해당하는 값들이 주어졌을 때 식을 계산하여 소수점 둘째 자리까지 출력하는 문제이다.
1. 중위 표기식이란?
중위 표기법은 우리가 흔히 사용하는 표기법으로 피연산자 사이에 연산자를 두는 방식이다.
3*5, 4+7, 5/2 등이 중위 표기식에 해당한다.
2. 후위 표기식이란?
후위 표기법은 연산자를 피연산자 뒤에 놓는 방법이다.
위의 중위 표기식을 후위 표기식으로 바꾸면 35*, 47+, 52/ 과 같은 형태로 적을 수 있다.
문제 풀이
후위 표기식을 계산하기 위해는 stack을 사용하는 것이 좋다.
더불어, 식의 결과와 중간 결과가 -20억보다 크거나 같고, 20억보다 작거나 같다고 했기 때문에 double 자료형을 써야 한다. (float을 쓰면 틀린다.)
후위 표기식을 string으로 입력받고 앞에서부터 차례로 한 글자씩 확인하며 처리한다.
해당 문자가 알파벳이라면 num배열에서 해당 알파벳에 대응하는 숫자를 불러와서 stack에 push 한다.
이때 num배열의 인덱스를 str[i]-'A' 과 같은 방식으로 적었는데, 이는 num배열에 숫자를 저장할 때, A에 해당하는 문자부터 차례로 저장되기 때문이다.
str[i]가 알파벳 A라면 'A'-'A'로 0이 나오기 때문에 num[0]에 접근할 수 있다.
str[i]가 알파벳 B라면 num[1]에 접근이 가능하다.
해당 문자가 기호라면 스택에서 가장 위에 두 숫자를 꺼내서 계산을 진행하고 결과를 다시 stack에 push 한다.
이때 먼저 꺼낸 숫자가 중위 표기식을 기준으로 했을 때 연산자 뒤에 오는 피연산자이다.
후위 표기식의 계산이 끝나면 stack에는 하나의 원소만 남게 된다.
이를 소수점 두 번째 자리까지 출력하면 문제를 해결할 수 있다.
코드
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
double calculate(char ch,double first,double second) {
if (ch == '+') return first + second;
if (ch == '-') return first - second;
if (ch == '*') return first * second;
if (ch == '/') return first / second;
}
int main() {
//입력
int n;
string str;
cin >> n >> str;
vector<int>num(n);
for (int i = 0; i < n; i++)cin >> num[i];
//문제 해결
double first,second;
stack<double>s;
for (int i = 0; i < str.size(); i++) {
if ('A'<=str[i] && str[i]<='Z') {//해당문자가 알파벳일때
s.push((double)num[str[i]-'A']); //num배열에서 숫자 가져와서 스택에 추가
}
else {//해당문자가 기호일때
second = s.top(); s.pop();
first = s.top(); s.pop();
s.push(calculate(str[i], first, second));
}
}
//결과 출력
double result = s.top();
printf("%.2f\n", result);
}
문제 코드 설명
1) calculate(char ch, double first, double second) 함수
연산자와 피연산자를 입력받아 계산을 진행하고 결과를 반환하는 함수이다.
2) 문제 해결
입력받은 후위 표기식(코드에서 str)을 앞에서부터 한 글자씩 읽으며 처리하기 위해 for문을 사용했다.
지금 처리하는 문자가 알파벳인지 기호인지를 구분하기 위해 조건문을 사용했다.
알파벳이라면 대응되는 숫자를 stack에 push()한다.
기호라면 stack에서 top()을 통해 가장 위의 값을 받아오고, pop()을 통해 그 값을 stack에서 삭제하는 과정을 두 번 진행하여 가장 위의 숫자 두 개를 받아온다.
그리고 계산을 진행한 결괏값을 다시 stack에 push()하면 된다.
3) 결과 출력
후위 표기식의 계산이 끝나면 stack에는 한 가지 요소만 남아있다.
이를 result 변수에 집어넣고, printf("%.2f\n")를 통해 소수점이 두 자리까지만 출력되도록 했다.
'알고리즘 > 코테 문제' 카테고리의 다른 글
[BOJ/백준 11726][C++] 2xn 타일링 (0) | 2022.02.04 |
---|---|
[BOJ/백준 2309][C++] 일곱 난쟁이 (0) | 2022.02.03 |
[BOJ/백준 9012][C++] 괄호 (0) | 2022.01.27 |
[BOJ/백준 11047][C++] 동전 0 (0) | 2022.01.26 |
[BOJ/백준 2231][C++] 분해합 (0) | 2022.01.25 |