13、スタックケース1:接尾辞式

問題源とアルゴリズムの構想は「網易雲教室:データ構造実戦完全マニュアル(夏曹俊・丁宋濤)」に由来する.
接尾辞式の要件
スタックの論理を用いて簡単な接尾辞式を実現する(最も一般的な算術論理表現方法)
接尾辞式のシーケンススタック実装
接尾辞式は、以前に実装された「シーケンススタック」の様々な操作によって実装されます.

/*         
    ：        ，         ；        
       ：
   1.     ，       ，       （          ）
   2.        ，        ，             ；
             ，           （   ，    ），              ，
       a.                ，                
       b.                ，             
                     ，            
                     
   3.          ，     ，              ，               ，
                 ，        
*/

//             
BOOL IsOperator(char ch)
{
    switch(ch)
    {
    case '+':
    case '-':
    case '*':
    case '/':
        return TRUE;
    default:
        return FALSE;
    }
}

//          （*、/    2；+、-    1）
int GetOperatorPriority(char ch)
{
    switch(ch)
    {
    case '+':
    case '-':
        return 1;
    case '*':
    case '/':
        return 2;
    default:
        return 0;
    }
}

//          ,      ，       0
int GetCurrentCalculatingResult(char ch, int operand1, int operand2)
{
    switch(ch)
    {
    case '+':
        return (operand2 + operand1);
    case '-':
        return (operand2 - operand1);
    case '*':
        return (operand2 * operand1);
    case '/':
        return (operand2 / operand1);
    default:
        return -1;
    }
}

//               ，     
int main()
{
    char expression[] = "8*9-4/2";
    int index = 0;//          
    int opera = 0;//    
    int operand1 = 0;//    1
    int operand2 = 0;//    2

    SequentialStack* pSqOperatorStack;//     
    SequentialStack* pSqOperandStack;//     

    pSqOperatorStack = (SequentialStack*)malloc(sizeof(SequentialStack));
    pSqOperandStack = (SequentialStack*)malloc(sizeof(SequentialStack));
    InitialStack(pSqOperatorStack);
    InitialStack(pSqOperandStack);

    while(expression[index] != '\0' && expression[index] != '
')
    {
        if(IsOperator(expression[index]) == TRUE)
        {
            if(!IsEmptyStack(pSqOperatorStack))
            {
                while((GetOperatorPriority(expression[index]) 
                    <= GetOperatorPriority(pSqOperatorStack->nStack[pSqOperatorStack->pTop])) 
                    && (!IsEmptyStack(pSqOperatorStack)))
                {
                    operand1 = PopStack(pSqOperandStack);
                    operand2 = PopStack(pSqOperandStack);
                    opera = PopStack(pSqOperatorStack);

                    PushStack(pSqOperandStack, GetCurrentCalculatingResult(opera, operand1, operand2));
                }
            }
            PushStack(pSqOperatorStack, expression[index]);
        }
        else
        {
            PushStack(pSqOperandStack, expression[index] - 48);
        }

        index++;
    }

    while(!IsEmptyStack(pSqOperatorStack))
    {
        opera = PopStack(pSqOperatorStack);
        operand1 = PopStack(pSqOperandStack);
        operand2 = PopStack(pSqOperandStack);

        PushStack(pSqOperandStack, GetCurrentCalculatingResult(opera, operand1, operand2));
    }

    printf("%d
", PopStack(pSqOperandStack));
    
    DestroyStack(pSqOperatorStack);
    DestroyStack(pSqOperandStack);

    system("pause");

    return 0;
}