---

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define MAX_STRING_SIZE 128

 

typedef enum

{

    lparen,     // 0

    rparen,     // 1

    plus,       // 2

    minus,      // 3

    times,      // 4

    divide,     // 5

    module,     // 6

    eos,        // 7

    operand     // 8

} precedence;

 

//  定義每一種運算的優先值 isp表示在stack的運算子的優先值，scp表示將要放進stack的運算子的優先值

//  順序為 "lparen,rparen,plus,minus,times,divide,module,eos,operand"

int isp[] = {0, 19, 12, 12, 13, 13, 13, 0, 0};

int icp[] = {20, 19, 12, 12, 13, 13, 13, 0, 0};

 

// infix轉postfix時會用到的node結構，先存入node後再堆入stack

// 根據演算法，只有運算子會被堆放進stack中，如果是數字則直接輸出

struct node

{

    precedence operator;

    struct node *next;

};

typedef struct node Node;

 

// 利用postfix進行五則運算時會用到的node結構

struct eval_node

{

    int number;

    struct eval_node *next;

};

typedef struct eval_node eval_Node;

 

// 初始化linked lists的頭

Node *head = NULL;

eval_Node *eval_head = NULL;

 

// 用來存放讀入的字串 (infix算式)

char expr[MAX_STRING_SIZE] = {0};

 

char symbol;        //Store the operator read from the infix string

precedence token;   //Store the value of the operator's enum

 

// 用來存放postfix的算式

char equation[MAX_STRING_SIZE] = {0};

 

int n = 0;          // Infix字串的索引

char temp[10];      // 存放數字用

 

// 可以從infix字串中讀取出一個運算子或數字

precedence getToken(void)

{

    symbol = expr[n];

    n++;

 

    switch (symbol)

    {

        case '(':

            return lparen;

        case ')':

            return rparen;

        case '+':

            return plus;

        case '-':

            return minus;

        case '/':

            return divide;

        case '*':

            return times;

        case '%':

            return module;

        case '\0':

            return eos;

        case '\n':

            return eos;

        default:

        {

            int i = 0;

            temp[i] = symbol;

            i++;

 

            // 判斷數字究竟是幾位數

            while (expr[n] >= '0' && expr[n] <= '9')

            {

                temp[i] = expr[n];

                i++;

                n++;

            }

            temp[i] = '\0';

 

            return operand;

        }

    }

}

 

// 將從infix中讀到的運算子放入堆疊

void push(precedence token)

{

    Node *new = (Node *)malloc(sizeof(Node));

    new->operator= token;

    new->next = head;

    head = new;

    return;

}

 

// 從堆疊中拿出一個運算子

precedence pop(void)

{

    precedence temp = head->operator;

    Node *current = head;

    head = head->next;

    free(current);

    return temp;

}

 

// 將堆疊中的運算子輸出至postfix的堆疊中

void printToken(precedence token)

{

    if (token == lparen)

        strcat(equation, "( ");

    else if (token == rparen)

        strcat(equation, ") ");

    else if (token == plus)

        strcat(equation, "+ ");

    else if (token == minus)

        strcat(equation, "- ");

    else if (token == divide)

        strcat(equation, "/ ");

    else if (token == times)

        strcat(equation, "* ");

    else if (token == module)

        strcat(equation, "% ");

    else

        return;

 

    return;

}

 

// 將infix轉換成postfix的主函式

void postfix(void)

{

    for (token = getToken(); token != eos; token = getToken())

    {

        if (token == operand)

        {

            strcat(equation, temp);

            strcat(equation, " ");

        }

 

        else if (token == rparen)

        {

            while (head->operator!= lparen)

                printToken(pop());

            pop();

        }

 

        else

        {

            // 判斷要放入堆疊的運算子的優先值有無大於目前堆疊頂的運算子的優先值

            while (isp[head->operator] >= icp[token])

                printToken(pop());

            push(token);

        }

    }

 

    // 將堆疊中剩下的運算子全部輸出至postfix中

    for (token = pop(); token != eos; token = pop())

        printToken(token);

 

    return;

}

 

// 將運算完的值堆入堆疊中

void eval_push(int input)

{

    eval_Node *new = (eval_Node *)malloc(sizeof(eval_Node));

    new->number = input;

    new->next = eval_head;

    eval_head = new;

    return;

}

 

// 將堆疊中的值拿出來

int eval_pop(void)

{

    int temp = eval_head->number;

    eval_Node *current = eval_head;

    eval_head = eval_head->next;

    free(current);

    return temp;

}

 

// 計算postfix值的主函式

int eval(void)

{

    int op1, op2;

    int i = 0;

    int input;

 

    // 持續計算直到讀到結尾為止

    while (equation[i] != '\0')

    {

        // 如果是數字的話，則放入堆疊之中

        if (equation[i] >= '0' && equation[i] <= '9')

        {

            input = atoi(equation + i);

            eval_push(input);

            while (equation[i] != ' ')

                i++;

        }

        // 根據讀到的運算子，來計算值

        else

        {

            op2 = eval_pop();

            op1 = eval_pop();

 

            if (equation[i] == '%')

                eval_push(op1 % op2);

            else if (equation[i] == '*')

                eval_push(op1 * op2);

            else if (equation[i] == '/')

                eval_push(op1 / op2);

            else if (equation[i] == '+')

                eval_push(op1 + op2);

            else if (equation[i] == '-')

                eval_push(op1 - op2);

 

            i++;

        }

        i++;

    }

 

    return (eval_pop());

}

 

// 去除字串中多餘的空白

void despace(void)

{

    int i=0, j=0;

 

    while(expr[j]!='\0')

    {

        if (expr[j]==' ')

        {

            j++;

            continue;

        }

 

        expr[i] = expr[j];

        i++;

        j++;

    }

    expr[i] = '\0';

}

 

int main()

{

    while (gets(expr) != NULL)

    {

        // 給堆疊一個初始化的頭，eos表示結束字元

        Node *top = (Node *)malloc(sizeof(Node));

        top->operator= eos;

        top->next = NULL;

        head = top;

 

        despace();

 

        // 將存放postfix的字串歸零

        strcpy(equation, "\0");

        n = 0;

 

        postfix();

        equation[strlen(equation) - 1] = '\0';  //把最後的空格移除

 

        printf("%d\n", eval());

    }

 

    return 0;

}