এক্সপ্রেশন পার্সিং#

একটি স্ট্রিং দেওয়া আছে যাতে সংখ্যা এবং বিভিন্ন অপারেটর সম্বলিত একটি গাণিতিক এক্সপ্রেশন আছে। আমাদের $O(n)$ সময়ে এর মান গণনা করতে হবে, যেখানে $n$ হলো স্ট্রিং-এর দৈর্ঘ্য।

এখানে আলোচিত অ্যালগরিদমটি একটি এক্সপ্রেশনকে তথাকথিত রিভার্স পোলিশ নোটেশনে রূপান্তর করে (স্পষ্ট বা অন্তর্নিহিতভাবে), এবং এই এক্সপ্রেশনটি মূল্যায়ন করে।

রিভার্স পোলিশ নোটেশন#

রিভার্স পোলিশ নোটেশন হলো গাণিতিক এক্সপ্রেশন লেখার একটি ফর্ম, যেখানে অপারেটরগুলো তাদের অপারেন্ডের পরে থাকে। উদাহরণস্বরূপ নিম্নলিখিত এক্সপ্রেশনটি

রিভার্স পোলিশ নোটেশনে নিম্নলিখিতভাবে লেখা যায়:

রিভার্স পোলিশ নোটেশন অস্ট্রেলিয়ান দার্শনিক ও কম্পিউটার বিজ্ঞান বিশেষজ্ঞ চার্লস হ্যাম্বলিন ১৯৫০-এর দশকের মাঝামাঝিতে পোলিশ নোটেশনের ভিত্তিতে তৈরি করেন, যেটি ১৯২০ সালে পোলিশ গণিতবিদ ইয়ান উকাশেভিচ প্রস্তাব করেছিলেন।

রিভার্স পোলিশ নোটেশনের সুবিধা হলো, এই আকারের এক্সপ্রেশনগুলো লিনিয়ার সময়ে মূল্যায়ন করা খুব সহজ। আমরা একটি স্ট্যাক ব্যবহার করি, যা প্রাথমিকভাবে খালি থাকে। আমরা রিভার্স পোলিশ নোটেশনের এক্সপ্রেশনের অপারেন্ড এবং অপারেটরগুলোর উপর ইটারেট করব। যদি বর্তমান উপাদানটি একটি সংখ্যা হয়, তাহলে আমরা মানটি স্ট্যাকের শীর্ষে রাখি, যদি বর্তমান উপাদানটি একটি অপারেটর হয়, তাহলে আমরা স্ট্যাক থেকে শীর্ষের দুটি উপাদান নিই, অপারেশনটি সম্পাদন করি, এবং ফলাফলটি আবার স্ট্যাকের শীর্ষে রাখি। শেষে স্ট্যাকে ঠিক একটি উপাদান থাকবে, যেটি হবে এক্সপ্রেশনের মান।

স্পষ্টতই এই সরল মূল্যায়ন $O(n)$ সময়ে চলে।

সরল এক্সপ্রেশন পার্সিং#

আপাতত আমরা শুধু একটি সরলীকৃত সমস্যা বিবেচনা করি: আমরা ধরে নিই যে সকল অপারেটর বাইনারি (অর্থাৎ তারা দুটি আর্গুমেন্ট নেয়), এবং সবগুলো লেফট-অ্যাসোসিয়েটিভ (যদি অগ্রাধিকার সমান হয়, তারা বাম থেকে ডানে কার্যকর হয়)। বন্ধনী অনুমোদিত।

আমরা দুটি স্ট্যাক সেট আপ করব: একটি সংখ্যার জন্য, এবং একটি অপারেটর ও বন্ধনীর জন্য। প্রাথমিকভাবে উভয় স্ট্যাক খালি। দ্বিতীয় স্ট্যাকের জন্য আমরা এই শর্ত বজায় রাখব যে সকল অপারেশন কঠোর অবনমনশীল অগ্রাধিকার অনুসারে সাজানো। যদি স্ট্যাকে বন্ধনী থাকে, তাহলে অপারেটরের প্রতিটি ব্লক (এক জোড়া বন্ধনীর সাথে সম্পর্কিত) সাজানো, এবং সম্পূর্ণ স্ট্যাক অগত্যা সাজানো নয়।

আমরা এক্সপ্রেশনের অক্ষরগুলোর উপর বাম থেকে ডানে ইটারেট করব। যদি বর্তমান অক্ষরটি একটি অঙ্ক হয়, তাহলে আমরা এই সংখ্যার মান স্ট্যাকে রাখি। যদি বর্তমান অক্ষরটি একটি ওপেনিং বন্ধনী হয়, তাহলে আমরা এটি স্ট্যাকে রাখি। যদি বর্তমান অক্ষরটি একটি ক্লোজিং বন্ধনী হয়, তাহলে আমরা ওপেনিং বন্ধনী না পাওয়া পর্যন্ত স্ট্যাকের সকল অপারেটর কার্যকর করি (অন্য কথায় আমরা বন্ধনীর ভিতরের সকল অপারেশন সম্পাদন করি)। সবশেষে যদি বর্তমান অক্ষরটি একটি অপারেটর হয়, তাহলে স্ট্যাকের শীর্ষে একই বা উচ্চতর অগ্রাধিকারের অপারেটর থাকা পর্যন্ত, আমরা সেই অপারেশন কার্যকর করব, এবং নতুন অপারেশনটি স্ট্যাকে রাখব।

সম্পূর্ণ স্ট্রিং প্রক্রিয়া করার পরে, কিছু অপারেটর এখনও স্ট্যাকে থাকতে পারে, তাই আমরা সেগুলো কার্যকর করি।

এখানে চারটি অপারেটর $+$ $-$ $*$ $/$ এর জন্য এই পদ্ধতির ইমপ্লিমেন্টেশন:

bool delim(char c) {
    return c == ' ';
}

bool is_op(char c) {
    return c == '+' || c == '-' || c == '*' || c == '/';
}

int priority (char op) {
    if (op == '+' || op == '-')
        return 1;
    if (op == '*' || op == '/')
        return 2;
    return -1;
}

void process_op(stack<int>& st, char op) {
    int r = st.top(); st.pop();
    int l = st.top(); st.pop();
    switch (op) {
        case '+': st.push(l + r); break;
        case '-': st.push(l - r); break;
        case '*': st.push(l * r); break;
        case '/': st.push(l / r); break;
    }
}

int evaluate(string& s) {
    stack<int> st;
    stack<char> op;
    for (int i = 0; i < (int)s.size(); i++) {
        if (delim(s[i]))
            continue;

        if (s[i] == '(') {
            op.push('(');
        } else if (s[i] == ')') {
            while (op.top() != '(') {
                process_op(st, op.top());
                op.pop();
            }
            op.pop();
        } else if (is_op(s[i])) {
            char cur_op = s[i];
            while (!op.empty() && priority(op.top()) >= priority(cur_op)) {
                process_op(st, op.top());
                op.pop();
            }
            op.push(cur_op);
        } else {
            int number = 0;
            while (i < (int)s.size() && isalnum(s[i]))
                number = number * 10 + s[i++] - '0';
            --i;
            st.push(number);
        }
    }

    while (!op.empty()) {
        process_op(st, op.top());
        op.pop();
    }
    return st.top();
}

এইভাবে আমরা $O(n)$-এ একটি এক্সপ্রেশনের মান গণনা করতে শিখলাম, একই সাথে আমরা পরোক্ষভাবে রিভার্স পোলিশ নোটেশন ব্যবহার করেছি। উপরের ইমপ্লিমেন্টেশনটি সামান্য পরিবর্তন করে রিভার্স পোলিশ নোটেশনে এক্সপ্রেশনটি স্পষ্ট আকারে পাওয়াও সম্ভব।

ইউনারি অপারেটর#

এখন ধরা যাক এক্সপ্রেশনে ইউনারি অপারেটরও আছে (যে অপারেটর একটি আর্গুমেন্ট নেয়)। ইউনারি প্লাস এবং ইউনারি মাইনাস এরকম অপারেটরের সাধারণ উদাহরণ।

এই ক্ষেত্রে একটি পার্থক্য হলো, আমাদের নির্ধারণ করতে হবে বর্তমান অপারেটরটি ইউনারি নাকি বাইনারি।

আপনি লক্ষ্য করতে পারেন যে, একটি ইউনারি অপারেটরের আগে সবসময় অন্য একটি অপারেটর বা একটি ওপেনিং বন্ধনী থাকে, অথবা কিছুই থাকে না (যদি এটি এক্সপ্রেশনের একেবারে শুরুতে থাকে)। বিপরীতে, একটি বাইনারি অপারেটরের আগে সবসময় একটি অপারেন্ড (সংখ্যা) বা একটি ক্লোজিং বন্ধনী থাকবে। তাই পরবর্তী অপারেটর ইউনারি হতে পারে কি না তা ফ্ল্যাগ করা সহজ।

অতিরিক্তভাবে, আমাদের একটি ইউনারি এবং একটি বাইনারি অপারেটর ভিন্নভাবে কার্যকর করতে হবে। এবং আমাদের ইউনারি অপারেটরের অগ্রাধিকার সকল বাইনারি অপারেটরের চেয়ে বেশি বেছে নিতে হবে।

এছাড়াও লক্ষ্য করা উচিত যে, কিছু ইউনারি অপারেটর (যেমন ইউনারি প্লাস এবং ইউনারি মাইনাস) আসলে রাইট-অ্যাসোসিয়েটিভ।

রাইট-অ্যাসোসিয়েটিভিটি#

রাইট-অ্যাসোসিয়েটিভ মানে হলো, যখনই অগ্রাধিকার সমান হয়, অপারেটরগুলো ডান থেকে বামে মূল্যায়িত হতে হবে।

উপরে উল্লেখ করা হয়েছে যে, ইউনারি অপারেটরগুলো সাধারণত রাইট-অ্যাসোসিয়েটিভ। রাইট-অ্যাসোসিয়েটিভ অপারেটরের আরেকটি উদাহরণ হলো ঘাত অপারেটর ($a \wedge b \wedge c$ সাধারণত $a^{b^c}$ হিসেবে বোঝা হয় এবং $(a^b)^c$ হিসেবে নয়)।

রাইট-অ্যাসোসিয়েটিভ অপারেটরগুলো সঠিকভাবে পরিচালনা করতে আমাদের কী পার্থক্য করতে হবে? দেখা যায় যে পরিবর্তনগুলো খুবই সামান্য। একমাত্র পার্থক্য হবে, যদি অগ্রাধিকার সমান হয় তাহলে আমরা রাইট-অ্যাসোসিয়েটিভ অপারেশনের কার্যকরকরণ স্থগিত করব।

শুধুমাত্র যে লাইনটি প্রতিস্থাপন করতে হবে তা হলো

while (!op.empty() && priority(op.top()) >= priority(cur_op))

এটি দিয়ে

while (!op.empty() && (
        (left_assoc(cur_op) && priority(op.top()) >= priority(cur_op)) ||
        (!left_assoc(cur_op) && priority(op.top()) > priority(cur_op))
    ))

যেখানে left_assoc হলো এমন একটি ফাংশন যা নির্ধারণ করে একটি অপারেটর লেফট-অ্যাসোসিয়েটিভ কিনা।

এখানে বাইনারি অপারেটর $+$ $-$ $*$ $/$ এবং ইউনারি অপারেটর $+$ ও $-$ এর জন্য একটি ইমপ্লিমেন্টেশন।

bool delim(char c) {
    return c == ' ';
}

bool is_op(char c) {
    return c == '+' || c == '-' || c == '*' || c == '/';
}

bool is_unary(char c) {
    return c == '+' || c=='-';
}

int priority (char op) {
    if (op < 0) // unary operator
        return 3;
    if (op == '+' || op == '-')
        return 1;
    if (op == '*' || op == '/')
        return 2;
    return -1;
}

void process_op(stack<int>& st, char op) {
    if (op < 0) {
        int l = st.top(); st.pop();
        switch (-op) {
            case '+': st.push(l); break;
            case '-': st.push(-l); break;
        }
    } else {
        int r = st.top(); st.pop();
        int l = st.top(); st.pop();
        switch (op) {
            case '+': st.push(l + r); break;
            case '-': st.push(l - r); break;
            case '*': st.push(l * r); break;
            case '/': st.push(l / r); break;
        }
    }
}

int evaluate(string& s) {
    stack<int> st;
    stack<char> op;
    bool may_be_unary = true;
    for (int i = 0; i < (int)s.size(); i++) {
        if (delim(s[i]))
            continue;

        if (s[i] == '(') {
            op.push('(');
            may_be_unary = true;
        } else if (s[i] == ')') {
            while (op.top() != '(') {
                process_op(st, op.top());
                op.pop();
            }
            op.pop();
            may_be_unary = false;
        } else if (is_op(s[i])) {
            char cur_op = s[i];
            if (may_be_unary && is_unary(cur_op))
                cur_op = -cur_op;
            while (!op.empty() && (
                    (cur_op >= 0 && priority(op.top()) >= priority(cur_op)) ||
                    (cur_op < 0 && priority(op.top()) > priority(cur_op))
                )) {
                process_op(st, op.top());
                op.pop();
            }
            op.push(cur_op);
            may_be_unary = true;
        } else {
            int number = 0;
            while (i < (int)s.size() && isalnum(s[i]))
                number = number * 10 + s[i++] - '0';
            --i;
            st.push(number);
            may_be_unary = false;
        }
    }

    while (!op.empty()) {
        process_op(st, op.top());
        op.pop();
    }
    return st.top();
}