a017: 五則運算

2019-08-03

內容

計算五則運算式的結果，包含加、減、乘、除、餘

輸入

輸入一個字串，其中包含運算元及運算子，為了方便讀取，所有的運算子及運算元均以空格區隔。

運算元為 0 ~231 -1 的整數

運算子則包含 + - * / % 及 ( )

運算時請注意先乘除後加減及() 優先運算的計算規則

2 + 3 _ 4
2 _ ( 3 + 4 ) * 5

輸出

輸出結果。為了避免小數點誤差，所有的運算過程都不會產生小數點，可以放心使用整數進行運算

14
70

解題思路

先把輸入的中序式轉成後序式，再解析後序式轉成整數。

完整程式碼

AC (1ms, 96KB)

#include <stdio.h>
#define MAX 10000

long long stack[MAX];
char infix[MAX], postfix[MAX], pTop;

char priority(char op)
{
    switch (op)
    {
    case '*': case '/': case '%':
        return 2;
    case '+': case '-':
        return 1;
    default:
        return 0;
    }
}

void inToPostfix(char* infix, char* postfix)
{
    int sTop = 0;
    char stack[MAX] = { 0 };
    pTop = 0;
    for (int i = 0; infix[i]; i++)
    {
        switch (infix[i])
        {
        case ' ':
            break;
        case '(':
            stack[++sTop] = infix[i];
            break;
        case ')':
            while (stack[sTop] != '(')
            {
                postfix[pTop++] = stack[sTop--];
            }
            sTop--;
            break;
        case '+': case '-': case '*': case '/': case '%':
            while (priority(infix[i]) <= priority(stack[sTop]))
            {
                postfix[pTop++] = stack[sTop--];
            }
            stack[++sTop] = infix[i];
            break;
        default:
            do
            {
                postfix[pTop++] = infix[i++];
            } while (infix[i] >= '0' && infix[i] <= '9');
            postfix[pTop++] = ' ';
            i--;
        }
    }
    while (sTop)
    {
        postfix[pTop++] = stack[sTop--];
    }
    postfix[pTop++] = '\0';
}

long long cale(long long lhs, long long rhs, char op)
{
    switch (op)
    {
    case '+': return lhs + rhs;
    case '-': return lhs - rhs;
    case '*': return lhs * rhs;
    case '/': return lhs / rhs;
    case '%': return lhs % rhs;
    }
    return -1;
}

long long postfixToInt(char* postfix)
{
    stack[0] = 0;
    int sTop = 0;
    char* now = postfix - 1;
    for (int i = 0; postfix[i]; i++)
    {
        if (postfix[i] >= '0' && postfix[i] <= '9')
        {
            stack[sTop] = stack[sTop] * 10 + (postfix[i] - '0');
        }
        else if (postfix[i] == ' ')
        {
            sTop++;
        }
        else
        {
            sTop--;
            stack[sTop - 1] = cale(stack[sTop - 1], stack[sTop], postfix[i]);
            stack[sTop] = 0;
        }
    }
    return stack[0];
}

int main()
{
    while (gets(infix) != NULL)
    {
        inToPostfix(infix, postfix);
        printf("%lld\n", postfixToInt(postfix));
    }
    return 0;
}