BITHU - Chiều cao cây biểu thức Dữ liệu vào: standard input Dữ liệu ra: standard output Giới hạn thời gian: 1.0 giây Giới hạn bộ nhớ: 128 megabyte Đăng bởi: ... Với mọi biểu thức số học gồm 5 phép toán hai ngôi +, -, *, /, ^, ta có thể xây dựng một cây nhị phân tương ứng. Ví dụ với biểu thức hậu tố: A B + C D E ^ - * thì cây nhị phân tương ứng là như sau: Yêu cầu: cho một biểu thức hậu tố, hãy xây dựng cây nhị phân tương ứng và tính chiều cao của cây. Dữ liệu nhập: - Là chuỗi biểu diễn biểu thức hậu tố gồm số hạng là các chữ cái latinh viết hoa và 5 phép toán +,-,*,/,^. Chiều dài tối đa của chuỗi là 1000. Giữa hai số hạng, hoặc giữa hai phép toán, hoặc giữa số hạng và phép toán, cách nhau một khoảng trắng. Ngoài ra không có ký tự khác. Dữ liệu cho đảm bảo biểu thức hậu tố là hợp lệ. Dữ liệu xuất: - Là số nguyên xác định chiều cao của cây nhị phân tương ứng. Ví dụ input A B + C D E ^ - * output 4 C++

$\color{#1fdb91}{\texttt{C}}\color{#0aaec9}{\texttt{+}}\color{#e9418e}{\texttt{+}}$
#include <bits/stdc++.h>

#define ll long long

using namespace std;

struct Node {
    string value;
    Node *LeftNode, *RightNode;
    
    void initValue(string val) {
        value = val;
    }
    void initLeftNode(Node* left) {
        LeftNode = left;
    }
    void initRightNode(Node* right) {
        RightNode = right;
    }
};

ll maxHeight(Node* btree) {
    ll res=1;
    if (btree->LeftNode != NULL) res = max(res, maxHeight(btree->LeftNode)+1);
    if (btree->RightNode != NULL) res = max(res, maxHeight(btree->RightNode)+1);
    return res;
}

bool isOperator(string val) {
    return (val == "+" || val == "-" || val == "*" || val == "/" || val == "^");
}

int main() {
    
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    queue<string> s;
    string inp, t; getline(cin, inp);
    stringstream ss(inp);
    
    while (ss >> t) s.push(t);
    
    stack<Node*> node;
    Node *tmp, *tmp1, *tmp2;
    while (!s.empty()) {
        string val = s.front();
        s.pop();
        tmp = new Node();
        tmp->initValue(val);
        if (!isOperator(val)) {
            node.push(tmp);
        } else {
            tmp1 = node.top();
            node.pop();
            tmp2 = node.top();
            node.pop();
            tmp->initLeftNode(tmp2);
            tmp->initRightNode(tmp1);
            node.push(tmp);
        }
    }
    
    cout << maxHeight(node.top());
    
}
$\\$
\begin{array}{c|c|c}\color{#ffd710}{\texttt{\{}} \color{#8655d6}{\texttt{\{}}\ \ \color{#8cdcda}{\text{Daoanhviet96}}\ \ \color{#8655d6}{\texttt{\}}} \color{#ffd710}{\texttt{\}}}\end{array}