당신들 이 원 하 는 접미사 표현 식 트 리

당신들 이 원 하 는 접미사 표현 식 트 리 Case Time Limit: 100 MS (Others) / 200 MS (Java) Case Memory Limit: 256 MB (Others) / 512 MB (Java) Accepted: 32 Total Submission: 141 내 제출 디 스 플레이 탭 보기 Problem 설명 은 이 진 트 리 한 그루 를 지정 하고 이 진 트 리 의 각 노드 는 네 개의 연산 자 +, -, *, / 를 표시 합 니 다.10 을 넘 지 않 는 비 마이너스 정 수 를 나타 내 든 가.이 두 갈래 나 무 를 접미사 표현 식 트 리 로 보고 대응 하 는 접미사 표현 식 과 이 접미사 표현 식 의 계산 결 과 를 출력 합 니 다.출력 접미사 표현 식 에 서 는 가장 바깥쪽 을 제외 하고 내부 의 모든 '왼쪽 연산 자 오른쪽 연산 자' 형식의 양측 에 작은 괄호 를 추가 해 야 합 니 다.예 를 들 어 2 + (3 * (4 / 5) 는 가능 한 정확 한 출력 이다.입력 파일 마다 한 그룹의 데 이 터 를 입력 합 니 다.첫 번 째 줄 의 정수 N (N < = 30) 은 이 진 트 리 의 결점 개수 (결점 번 호 는 0 에서 N - 1) 를 나타 낸다.두 번 째 줄 은 결점 번호 에 따라 작은 것 부터 큰 것 까지 N 개의 결점 의 값 (빈 칸 으로 분리) 을 제시 합 니 다. 그것 은 네 개의 연산 자 +, -, *, / 의 하나 이거 나 10 을 초과 하지 않 는 비 마이너스 정수 입 니 다.다음은 노드 번호 에 따라 어 릴 때 부터 큰 순서 로 N 줄 을 주 고, 행동 마다 두 개의 번 호 를 주 며, 각각 이 노드 의 왼쪽 아이 번호 와 오른쪽 아이 번 호 를 나타 내 며, 왼쪽 (오른쪽) 아이 가 존재 하지 않 는 다 면 문자 '-' 로 대신한다.데이터 보증 번 호 는 0 에서 N - 1 사이 이 며, 접미사 표현 식 트 리 는 반드시 합 법 적 입 니 다.출력 한 줄, 즉 원 하 는 접미사 표현 식 과 대응 하 는 계산 결과 (정밀도 유지 두 소수), 표현 식 과 계산 결과 사 이 를 빈 칸 으로 구분 합 니 다.출력 접두사 표현 식 에 빈 칸 이 있 으 면 안 됩 니 다.데 이 터 는 접두사 표현 식 이 합 법 적 이 고 계산 과정 에서 0 으로 나 누 는 상황 이 발생 하지 않 습 니 다.Sample Input 5 * 3 + 4 6 1 2 - 3 4 - Sample Output 3 * (4 + 6) 30.00 Author Shoutmon Source 17 절 대 대학원 시험 모 의 경기
사고, 접두사 표현 식 은 좋 은 공 입 니 다. 나 무 를 만 든 후에 바로 중간 순서 로 옮 겨 다 니 면 됩 니 다. 그 다음 에 가장 바깥쪽 괄호 를 없 애고 string 으로 쉽게 실현 할 수 있 습 니 다. 어 려 운 점 은 값 을 구 하 는 것 입 니 다. 문제 의 수치 가 0 보다 크 면 10 보다 작 기 때문에 두 자리 가 나타 날 수 있 습 니 다. 그래서 char 로 수치 와 계산 기 호 를 저장 할 수 있 습 니 다. 이번 실현 은 flag 를 통 해 연산 자 여 부 를 판단 할 수 있 습 니 다.따라서 코드 가 많 기 때문에 수치 도 char 에 저장 할 수 있 습 니 다. 여기 서 설명 하지 않 습 니 다.

#define _CRT_SECURE_NO_WARNINGS
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int MaxN = 36;
int N;
struct node {
    int data;
    bool sign;
    char s;
    int lchild;
    int rchild;
    node() { rchild = lchild = -1; sign = false; }
}Node[MaxN];

bool isRoot[MaxN];
string res;

string IntToStr(int num) {
    string str;
    while (num) {
        str.insert(str.begin(),num % 10 + '0');
        num /= 10;
    }
    if (!str.size()) return "0";
    return str;
}

double post(int root) {
    if (-1 == root) return 0;
    bool flag = (Node[root].lchild != -1 || Node[root].rchild != -1);
    if (flag) res += "(";

    double leftv = post(Node[root].lchild);
    if (Node[root].sign) res += Node[root].s;
    else res += IntToStr(Node[root].data);

    double rightv = post(Node[root].rchild);

    if (flag) res += ")";

    if (!Node[root].sign) return Node[root].data;
    else {
        switch (Node[root].s)
        {
        case '+':return leftv + rightv;
        case '-':return leftv - rightv;
        case '*':return leftv * rightv;
        case '/':return leftv / rightv;
        default:
            return 0;
        }
    }
}


int main() {
#ifdef _DEBUG
    freopen("data.txt", "r+", stdin);
#endif // _DEBUG
    std::ios::sync_with_stdio(false);

    stringstream ss; string str; int idx = 0;
    cin >> N; cin.get(); getline(cin, str); ss << str;
    for (int i = 0; i < N; ++i) {
        if ('0' <= str[idx] && str[i] <= '9') {
            ss >> Node[i].data;
        }
        else {
            char ch;
            ss >> ch;
            Node[i].s = ch;
            Node[i].sign = true;
        }
        while (idx < str.size()-1 && str[idx] != ' ')++idx;
        if (idx < str.size() - 1) ++idx;
    }
    memset(isRoot, 1, N + 1);
    for (int i = 0; i < N; ++i) {
        ss.clear(); ss.str("");
        getline(cin, str); ss << str;
        int idx = 0, lc, rc;
        if (str[idx] == '-') {
            ss.get();
            ++idx;
        }
        else {
            ss >> Node[i].lchild;
            isRoot[Node[i].lchild] = false;
        }

        while (str[idx] != ' ')++idx;
        ++idx;

        if (str[idx] != '-') {
            ss >> Node[i].rchild;
            isRoot[Node[i].rchild] = false;
        }
    }

    int root = 0;
    while (!isRoot[root])++root;

    double val = post(root);

    if (res.size() >= 3) {
        res.erase(res.begin());
        res.erase(res.end()-1);
    }
    cout << res << " " ;
    cout << setiosflags(ios::fixed) << setprecision(2) << val;
    return 0;
}