数据结构-栈的应用-表达式求值

#include <stdio.h>
#include <malloc.h>

#define OK 0
#define ERROR 1

/*----------字符栈--------*/
typedef char EType;

typedef struct{
    EType *data;
    int capacity;
    EType *top;
}SqStack;

int initSqStack(SqStack *pS,int size){
   pS->data = (EType*)malloc(size*sizeof(EType));
   if(!pS->data) return ERROR;
   pS->capacity = size;
   pS->top = pS->data;
   return OK;
}

int pushSqStack(SqStack *pS,EType e){
    if(pS->top-pS->data==pS->capacity)
        return ERROR;
    *(pS->top) = e;
    pS->top++;
    return OK;
}

int popSqStack(SqStack *pS){
    if(pS->top==pS->data)
        return ERROR;
    pS->top--;
    return OK;
}
int topSqStack(SqStack *pS,EType *e){
    if(pS->top==pS->data)
        return ERROR;
    *e = *(pS->top-1);
    return OK;
}

int isEmptySqStack(SqStack S){
    if(S.top==S.data) return 1;
    return 0;
}



/*----------整数栈--------*/
typedef int Type;

typedef struct{
    Type *data;
    int capacity;
    Type *top;
}Stack;

int initStack(Stack *pS,int size){
   pS->data = (Type*)malloc(size*sizeof(Type));
   if(!pS->data) return ERROR;
   pS->capacity = size;
   pS->top = pS->data;
   return OK;
}

int pushStack(Stack *pS,Type e){
    if(pS->top-pS->data==pS->capacity)
        return ERROR;
    *(pS->top) = e;
    pS->top++;
    return OK;
}

int popStack(Stack *pS){
    if(pS->top==pS->data)
        return ERROR;
    pS->top--;
    return OK;
}
int topStack(Stack *pS,Type *e){
    if(pS->top==pS->data)
        return ERROR;
    *e = *(pS->top-1);
    return OK;
}

int isEmptyStack(Stack S){
    if(S.top==S.data) return 1;
    return 0;
}



/*----- 中缀表达式求值--- */

char op_prior_table[][7] = {
    { '>','>','<','<','<','>','>' },
    { '>','>','<','<','<','>','>' },
    { '>','>','>','>','<','>','>' },
    { '>','>','>','>','<','>','>' },
    { '<','<','<','<','<','=','!' },
    { '>','>','>','>','!','>','>' },
    { '<','<','<','<','<','!','=' }
};

int index_of_op(const char op){
    if(op=='+') return 0;
    else if(op=='-') return 1;
    else if(op=='*') return 2;
    else if(op=='/') return 3;
    else if(op=='(') return 4;
    else if(op==')') return 5;
    else             return 6;   /* '#' */ 
}

int prior(const char op1,const char op2){
    int i = index_of_op(op1),j = index_of_op(op2);
    char cmp = op_prior_table[i][j];
    if(cmp=='>') return 1;
    else if(cmp=='<') return -1;
    else if(cmp=='=') return 0;
    return 10000; /*不会出现的情况 */
}

/*用算符op对两个运算数进行运算 : n1 op n2 */

int op2num(const char op,int n1, int n2){
    if(op=='+') return n1+n2;
    //...此处补充你的代码 
}

int compute_mid_expression(const char *exp){
    initSqStack(&op_stack,100);
    initStack(&num_stack,100);
    
    const char *p = exp;
    pushSqStack( &op_stack,'#');
    while(*p!='\0'){
        if( *p>='0'&&*p<='9' )  { /* 运算数 */
            pushStack( &num_stack,*p-'0'); /*运算数直接入栈*/             
            p++;
        }
        else {//运算符             
            char op1 = topSqStack(&op_stack);
            int priority =  prior(op1,*p);

            if(priority==1 ){/*栈顶算符优先，需要立即弹出进行计算了*/
                popSqStack(&op_stack); 
                /*... 加入你的代码*/             
            }
            else if(priority==-1 ){ /*当前算符*p优先*/
                pushSqStack( &op_stack,*p); 
                p++; /*消去栈顶，移到下一个字符 */
            }
            else if(priority==0 ){
                /*... 加入你的代码*/
            }            
        }
    }
}

int main()
{
    char *express = "3*(2+4)-8/2#";
    cout<<compute_mid_expression(express)<<"\n";
    return 0;
}