[백준 알고리즘] 1935번: 후위 표기식2
April 04, 2021
https://www.acmicpc.net/problem/1935
문제
문제
후위 표기식과 각 피연산자에 대응하는 값들이 주어져 있을 때, 그 식을 계산하는 프로그램을 작성하시오.
입력
첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다. 그리고 둘째 줄에는 후위 표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이는 100을 넘지 않는다) 그리고 셋째 줄부터 N+2번째 줄까지는 각 피연산자에 대응하는 값이 주어진다. (3번째 줄에는 A에 해당하는 값, 4번째 줄에는 B에 해당하는값 , 5번째 줄에는 C …이 주어진다, 그리고 피연산자에 대응 하는 값은 정수이다)
출력
계산 결과를 소숫점 둘째 자리까지 출력한다.
풀이
후위표기식의 계산 방법을 그대로 따르되, 각 문자에 대한 정수 정보만 잘 기억해두면 된다. 후위표기식은 아래와 같이 계산한다.
- 식을 왼쪽에서부터 읽으면서 피연산자가 나오면 스택에 넣는다.
- 연산자가 나오면 스택에 있는 두 요소를 꺼내서 계산한다. 이때, 스택에 먼저 들어간 값을 왼쪽 피연산자로 삼는다.
- 계산이 끝나면 계산 결과를 스택에 다시 넣는다.
- 1 ~ 3 을 식의 끝에 도달할 때까지 반복하면 스택에 최종 결과 값이 남는다.
문제에서 소수점 둘째 자리까지 출력하라고 했기 때문에 포맷을 정하기 쉬운 printf 함수로 최종 결과를 출력했다.
코드
#include <iostream>
#include <cstdio>
#include <stack>
#include <string>
#include <vector>
using namespace std;
int main() {
int N;
string str;
vector<double> operands(27, 0);
stack<double> stk;
cin >> N >> str;
for (char c : str) {
if (c != '-' && c != '*' && c != '+' && c != '/') {
if (operands[c - 65] == 0) {
int n;
cin >> n;
operands[c - 65] = n;
}
}
}
for (char c : str) {
if (c != '-' && c != '*' && c != '+' && c != '/') {
stk.push(operands[c - 65]);
}
else {
auto rhs = stk.top();
stk.pop();
auto lhs = stk.top();
stk.pop();
switch (c) {
case '-':
stk.push(lhs - rhs);
break;
case '+':
stk.push(lhs + rhs);
break;
case '*':
stk.push(lhs * rhs);
break;
case '/':
stk.push(lhs / rhs);
break;
}
}
}
printf("%0.2f\n", stk.top());
}
