#include<iostream>

#include <stdlib.h>

using namespace std;

typedef int Status;

const int TRUE=;

const int FALSE=;

const int OK=;

const int ERROR=;

const int INFEASIBLE=-;

const int overflow=-;

const int STACK_INIT_SIZE=;

const int STACKINCREMENT=;

typedef struct{

    char *base;

    char *top;

    int stacksize;

}SqStack;

//构造一个空栈

Status InitStack(SqStack &S)

{

    S.base=(char*)malloc(sizeof(char)*STACK_INIT_SIZE);

    if(!S.base) exit(overflow);

    S.top=S.base;

    S.stacksize=STACK_INIT_SIZE;

    return OK;

}

Status GetTop(SqStack S,char &e)

{

    if(S.top==S.base) return ERROR;

    e=*(S.top-);

    return OK;

}

Status Push(SqStack &S,char e)

{

    if(S.top-S.base>=S.stacksize)

    {

        S.base=(char*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(char));

        if(!S.base)exit(overflow);

        S.top=S.base+S.stacksize;

        S.stacksize+=STACKINCREMENT;

    }

    *S.top++=e;

    return OK;

}

Status Pop(SqStack &S,char &e)

{

    if(S.top==S.base) return ERROR;

    e=*--S.top;

    return OK;

}

Status StackEmpty(SqStack S){

    if(S.base==S.top)

        return TRUE;

    else

        return FALSE;

}

Status ClearStack(SqStack &S)

{

    S.top = S.base ;

    return TRUE;

}

Status DestroyStack(SqStack &S)

{

    if(S.base!=NULL)

    {

        free(S.base);

        S.stacksize=;

        S.top=NULL;

    }

    return TRUE;

}

#include"book3_3.h"

#define ND 0  //操作数标志

#define TR 1  //操作符标志

//存放运算符的优先顺序的矩阵 op1是竖排的 op2是横排的 e表示错误

const static char Order[][]=

    {{'>','>','<','<','<','>','>'}, // +

     {'>','>','<','<','<','>','>'}, // -

     {'>','>','>','>','<','>','>'}, // *

     {'>','>','>','>','<','>','>'}, // /

     {'<','<','<','<','<','=','e'}, // (

     {'>','>','>','>','e','>','>'}, // )

     {'<','<','<','<','<','e','='}}; // #

//     +   -   *   /   (   )   #       

//比较两个操作符的优先级 op1和op2的顺序不能错

Status compOperator(char op1, char op2, char &result)

{

    int t1=,t2=;

    //找到两个操作符的优先级在矩阵中的位置

    switch(op1)

    {

    case '+': t1=; break;

    case '-': t1=; break;

    case '*': t1=; break;

    case '/': t1=; break;

    case '(': t1=; break;

    case ')': t1=; break;

    case '#': t1=; break;

    default: return ERROR; break;

    }

    switch(op2)

    {

    case '+': t2=; break;

    case '-': t2=; break;

    case '*': t2=; break;

    case '/': t2=; break;

    case '(': t2=; break;

    case ')': t2=; break;

    case '#': t2=; break;

    default: return ERROR; break;

    }

    result=Order[t1][t2];

    if(result=='e')

        return ERROR;

    else

        return OK;

}

int decideNDorTR(char t)  //判断输入的字符是操作符还是操作数

{

    if(t>=&&t<=)  //数字的ascii码范围

    {

        return ND;

    }

    else if(t=='+' || t=='-' || t=='*' || t=='/' || t=='(' || t==')' || t=='#')

    {

        return TR;

    }

    else

    {

        printf("error");

        return ERROR;

    }

}

char myCalculate(char op,char num1,char num2)  //字符型的运算符的计算

{

    char num;

    switch(op)

    {

    case '+': num= num1+ num2; break;

    case '-': num= num1- num2; break;

    case '*': num= num1* num2; break;

    case '/': num= num1/ num2; break;

    default: printf("error");break;

    }

    return num;

}

//计算表达式的函数 注意运算结果大小不能超过255 char型

char EvaluateExpression(char *p, int length)

{

    SqStack OPTR, OPND;

    InitStack(OPTR);

    InitStack(OPND);

    Push(OPTR,'#');

    while(*p != '\0')

    {

        char t = *(p++);

        int ND_TR=decideNDorTR(t); //判断是操作符 还是 操作数

        if(ND_TR == ND) //操作数

        {

            //操作数有可能是多位的

            char num=;

            while(t>=&&t<=) //字符 0-9

            {

                num = num *  + t - ;

                t=*(p++);

            }

            p--; //对于 12+3 这样的情况 在取完数后 p=3  +被取走了 需要退一个 把操作符还回去

            Push(OPND,num);

        }

        else if(ND_TR == TR) //操作符

        {

            char order;

            char op1;

            char op2= t;

            GetTop(OPTR,op1);

            compOperator(op1, op2, order);

            switch(order)

            {

            case '>':   //若栈中的操作符优先级高 则取出操作数的前两个做运算 把运算后的操作符弹出  运算结果压入

                {

                    char num1,num2,num;

                    char tmp;

                    Pop(OPND,num2);

                    Pop(OPND,num1);

                    num = myCalculate(op1,num1,num2);

                    Push(OPND,num);

                    Pop(OPTR,tmp);

                    p--; //这里p要退回 让op2再进行新一轮判断

                    break;

                }

            case '<': //若栈中操作符优先级低 新操作符进栈

                {

                    Push(OPTR,op2);

                    break;

                }

            case '=': //（）或# 弹出 脱括号

                {

                    char tmp;

                    Pop(OPTR,tmp); break;

                }

            default:

                {

                    break;

                }

            }

        }

    }

    char e;

    GetTop(OPND,e);

    return e;

}

void main()

{

    char p[]="(11+2)*3-28+123-52#";

    char ans;

    ans = EvaluateExpression(p, );

    printf("%d",ans);

    getchar();

}