پرش به محتویات

تجزیه عبارت

رشته‌ای حاوی یک عبارت ریاضی شامل اعداد و عملگرهای مختلف داده شده است. باید مقدار آن را در زمان $O(n)$ محاسبه کنیم، که در آن $n$ طول رشته است.

الگوریتمی که در اینجا بحث می‌شود، یک عبارت را به اصطلاح به نشانه گذاری لهستانی معکوس (به صورت صریح یا ضمنی) ترجمه کرده و سپس این عبارت را ارزیابی می‌کند.

نشانه گذاری لهستانی معکوس

نشانه گذاری لهستانی معکوس، شکلی از نوشتن عبارات ریاضی است که در آن، عملگرها بعد از عملوندهای خود قرار می‌گیرند. برای مثال، عبارت زیر

$$a + b * c * d + (e - f) * (g * h + i)$$

می‌تواند به صورت زیر در نشانه گذاری لهستانی معکوس نوشته شود:

$$a b c * d * + e f - g h * i + * +$$

نشانه گذاری لهستانی معکوس توسط فیلسوف و متخصص علوم کامپیوتر استرالیایی، چارلز همبلین، در اواسط دهه ۱۹۵۰ بر اساس نشانه گذاری لهستانی توسعه یافت که در سال ۱۹۲۰ توسط ریاضیدان لهستانی، یان ووکاشویچ، پیشنهاد شده بود.

راحتی نشانه گذاری لهستانی معکوس در این است که عبارات در این شکل، بسیار آسان ارزیابی می‌شوند و این کار در زمان خطی انجام‌پذیر است. ما از یک پشته استفاده می‌کنیم که در ابتدا خالی است. ما روی عملوندها و عملگرهای عبارت در نشانه گذاری لهستانی معکوس پیمایش می‌کنیم. اگر عنصر فعلی یک عدد باشد، مقدار آن را بالای پشته قرار می‌دهیم. اگر عنصر فعلی یک عملگر باشد، دو عنصر بالای پشته را برداشته، عملیات را انجام می‌دهیم و نتیجه را دوباره به بالای پشته برمی‌گردانیم. در پایان، دقیقاً یک عنصر در پشته باقی می‌ماند که همان مقدار عبارت خواهد بود.

بدیهی است که این ارزیابی ساده در زمان $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();
}