문제

후위 표기식과 각 피연산자에 대응하는 값들이 주어져 있을 때, 그 식을 계산하는 프로그램을 작성하시오.

입력

첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다. 그리고 둘째 줄에는 후위 표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이는 100을 넘지 않는다) 그리고 셋째 줄부터 N+2번째 줄까지는 각 피연산자에 대응하는 값이 주어진다. 3번째 줄에는 A에 해당하는 값, 4번째 줄에는 B에 해당하는 값, 5번째 줄에는 C ...이 주어진다, 그리고 피연산자에 대응하는 값은 100보다 작거나 같은 자연수이다.

후위 표기식을 앞에서부터 계산했을 때, 식의 결과와 중간 결과가 -20억보다 크거나 같고, 20억보다 작거나 같은 입력만 주어진다.

출력

• 계산 결과를 소숫점 둘째 자리까지 출력한다.

---

1. 아이디어 및 실수

• 아이디어:
  • 스택을 활용하여 대문자가 나오면 수를 쌓고, 연산자가 나오면 스택에서 가장 위의 두 수를 pop해주어 해당 연산 진행 후 다시 push하는 방식
  • 후위 표기식에 대문자와 연산자가 섞여나오는데, 이는 ASCII 코드를 활용하여 구분한다.
• 실수: 아이디어의 방향성은 맞았지만, 역시 사소하게 놓친 부분이 있었다.
  • 출력조건의 소숫점 둘째자리까지 출력을 못봤다. (따라서, 정답부분을 그냥 %f로 출력했었는데 나중에 %.2f로 수정해줌)
  • AA+A+와 같이 총 피연산자의 개수(1)와 알파벳의 등장 횟수(3)가 맞지 않는 경우를 고려하지 않았었다. 그래서 알파벳이 나올때마다 피연산자가 저장된 배열에서 index를 증가시키며 하나씩 스택에 push해주었었다.
    (아래 코드의 operIdx가 index 역할)

#include <iostream> #include <stack> #include <cstring> using namespace std; int main() { //operands: 피연산자들(숫자)을 저장하는 배열 //formula: 후위표기식을 저장하는 배열 //a, b: 스택에서 계산할 두 개의 피연산자 //operIdx: operands 배열을 탐색할 인덱스 변수 int N; double a, b; int operIdx = 0; double operands[26]; char formula[100]; stack<double> cal; //N, 후위표기식, 피연산자들을 입력받는다. scanf("%d", &N); scanf("%s", formula); for (int i = 0; i < N; i++) { scanf("%lf", &operands[i]); } //후위 표기식에서 알파벳과 연산자를 구분하여 숫자들을 스택에 쌓고, 계산하여 넣는다. for (int i = 0; i < strlen(formula); i++) { //표기식에서 현재 위치가 알파벳을 가리킨다면, 스택에 피연산자(숫자)를 쌓는다. if (formula[i] >= 65 && formula[i] <= 90) cal.push(operands[operIdx++]); //표기식에서 현재 위치가 연산자를 가리킨다면, 스택에 쌓인 두 숫자를 꺼내 연산하고 다시 push한다. else if (formula[i] == '+') { ... } else if (formula[i] == '-') { ... } else if (formula[i] == '*') { ... } else if (formula[i] == '/') { ... } } printf("%f\n", cal.top()); }

2. 최종 소스코드 및 해결방법

• 해결방법:
  • 대문자 알파벳의 ASCII 코드와 피연산자 배열의 인덱스를 연결시켜주었다. 그러면 해당 알파벳에 대응하는 피연산자가 생기는 셈이다. 예를 들어, A의 ASCII 코드는 65이므로, A에 대응하는 피연산자를 얻으려면 피연산자 배열에서 (int)A - 65를 하면 된다. 마찬가지로, 다른 대문자들도 int로 변환시킨 해당 대문자의 ASCII코드 - 65를 하면 대응하는 피연산자를 얻을 수 있다. 최종 소스코드는 아래와 같다.

#include <iostream> #include <stack> #include <cstring> using namespace std; int main() { //operands: 피연산자들(숫자)을 저장하는 배열 //formula: 후위표기식을 저장하는 배열 //a, b: 스택에서 계산할 두 개의 피연산자 int N; double a, b; double operands[26]; char formula[100]; stack<double> cal; //N, 후위표기식, 피연산자들을 입력받는다. scanf("%d", &N); scanf("%s", formula); for (int i = 0; i < N; i++) { scanf("%lf", &operands[i]); } //후위 표기식에서 알파벳과 연산자를 구분하여 숫자들을 스택에 쌓고, 계산하여 넣는다. for (int i = 0; i < strlen(formula); i++) { //표기식에서 현재 위치가 알파벳을 가리킨다면, 스택에 피연산자(숫자)를 쌓는다. if (formula[i] >= 65 && formula[i] <= 90) { int index = (int)formula[i] - 65; cal.push(operands[index]); } //표기식에서 현재 위치가 연산자를 가리킨다면, 스택에 쌓인 두 숫자를 꺼내 연산하고 다시 push한다. else if (formula[i] == '+') { a = cal.top(); cal.pop(); b = cal.top(); cal.pop(); cal.push(b + a); } else if (formula[i] == '-') { a = cal.top(); cal.pop(); b = cal.top(); cal.pop(); cal.push(b - a); } else if (formula[i] == '*') { a = cal.top(); cal.pop(); b = cal.top(); cal.pop(); cal.push(b * a); } else if (formula[i] == '/') { a = cal.top(); cal.pop(); b = cal.top(); cal.pop(); cal.push(b / a); } } printf("%.2f\n", cal.top()); }