大神的世界

後序演算法

迴圈

輸入字串

利用自串串流分段

判別此段為數字或符號

數字

計算出來並放入數字陣列

符號

判別+-*/%()

若為+-且不是第一個

則前面+-*/%皆可執行

若為*/%且不是第一個

則前面*/%可執行

若為(

則直接存入

若為)

則執行至(

此處運算必定只剩+-

若是第一個

則直接存入

離開迴圈後(沒東西了)

把剩下的做完 (其實也只剩一個運算)

#include <iostream>
#include <cstring>
#include <sstream>
#include <cctype>

using namespace std;

void init();
void getOperands(string oper);
int priority(char operators);
void calc(char operators);

int operands[1000];
char operators[1000];
int operators_length;
int operands_length;
stringstream ss;

int main()
{

    string str;
    string oper;

    while(getline(cin , str))
    {
        init();
        ss.str(str);

        while(ss >> oper)
        {
            if(isdigit(oper[0]))
                getOperands(oper);
            else
            {
                switch(oper[0])
                {
                    case '+': case '-':

                        while(operators_length > 0 && priority(operators[operators_length-1]) > 1)
                            calc(operators[operators_length - 1]);

                        operators[operators_length++] = oper[0];
                        break;

                    case '*': case '/': case '%':

                        while(operators_length > 0 && priority(operators[operators_length-1]) == 2)
                            calc(operators[operators_length-1]);

                        operators[operators_length++] = oper[0];
                        break;

                    case '(':

                        operators[operators_length++] = oper[0];
                        break;

                    case ')':

                        for(int i = operators_length - 1; operators[i] != '('; i--)
                            calc(operators[i]);

                        operators_length--;
                        break;
                }
            }
        }

        for(operators_length-- ; operators_length >= 0;)
            calc(operators[operators_length]);

        cout << operands[0] << endl;
    }

    return 0;

}

void init()
{
    memset(operands , 0, sizeof(operands));
    memset(operators, 0, sizeof(operators));
    ss.clear();
    operands_length = operators_length = 0;
}

void getOperands(string oper)
{
    int number = 0;
    for(int i = 0; i<oper.length(); i++)
    {
        number *= 10;
        number += oper[i] - '0';
    }
    operands[operands_length++] = number;;
}

int priority(char operators)
{
    switch(operators)
    {
        case '+':case '-':
            return 3;

        case '*':case '/': case '%':
            return 2;

        case '(':case')':
            return 1;

        default:
            return 0;
    }
}

void calc(char operators)
{
    switch(operators)
    {
        case '+':
            operands[operands_length - 2] += operands[operands_length - 1];
            operators_length--;
            operands_length--;
            break;

        case '-':
            operands[operands_length - 2] -= operands[operands_length - 1];
            operators_length--;
            operands_length--;
            break;

        case '*':
            operands[operands_length - 2] *= operands[operands_length - 1];
            operators_length--;
            operands_length--;
            break;

        case '/':
            operands[operands_length - 2] /= operands[operands_length - 1];
            operators_length--;
            operands_length--;
            break;

        case '%':
            operands[operands_length - 2] %= operands[operands_length - 1];
            operators_length--;
            operands_length--;
            break;

        default: break;
    }
}