高中生程式解題系統:後序運算法

若您覺得文章寫得不錯,請點選文章上的廣告,來支持小編,謝謝。

題目連結 https://zerojudge.tw/ShowProblem?problemid=d016

後序表示法的運算方式如下:
從後序表示法的前方開始讀取,
若是運算元則放進堆疊裡,
若是運算子,則從堆疊取出兩個運算元進行運算,並將結果存回堆疊,
若讀取完畢,則堆疊的最頂端即為此後序表示式的運算結果。

例子可看底下影片的動畫說明:

底下程式碼是用STL裡的stack來做。此外,程式碼的寫法是可以改善的。

程式碼:
#include <iostream>
#include <string>
#include <sstream>
#include <stack>

using namespace std;

int main(){

    string input;

    while( getline(cin, input) )
    {
        stack<int> value;

        stringstream strStream(input);
        string token;
        int inStack;
        int outStack;

        while( strStream >> token )
        {
            switch(token[0])
            {
                case '+':
                    outStack = value.top();
                    value.pop();
                    inStack = value.top();
                    value.pop();
                    inStack += outStack;
                    value.push(inStack);
                    break;
                case '-':
                    outStack = value.top();
                    value.pop();
                    inStack = value.top();
                    value.pop();
                    inStack -= outStack;
                    value.push(inStack);
                    break;
                case '*':
                    outStack = value.top();
                    value.pop();
                    inStack = value.top();
                    value.pop();
                    inStack *= outStack;
                    value.push(inStack);
                    break;
                case '/':
                    outStack = value.top();
                    value.pop();
                    inStack = value.top();
                    value.pop();
                    inStack /= outStack;
                    value.push(inStack);
                    break;
                case '%':
                    outStack = value.top();
                    value.pop();
                    inStack = value.top();
                    value.pop();
                    inStack %= outStack;
                    value.push(inStack);
                    break;
                default:
                    inStack = atol(token.c_str());
                    value.push(inStack);
                    break;
            }
        }

        inStack = value.top();
        cout << inStack << endl;
    }

    return 0;
}

沒有留言: