栈实现算术优先级运算c++

#include <stdlib.h>
#include <stdio.h>
#include <iostream>
using namespace std;

#define STACK_INIT_SIZE 100   //栈初始开辟空间大小
#define STACK_INCREMENT 10    //栈追加空间大小

//优先级数组，2表示top>c，1表示top<c，0表示top=c，-1表示错误
int prior[7][7] = { {2,2,1,1,1,2,2},{2,2,1,1,1,2,2},{2,2,2,2,1,2,2},
{2,2,2,2,1,2,2},{1,1,1,1,1,0,-1},{2,2,2,2,-1,2,2},{1,1,1,1,1,-1,0} };

//******************************************************************
//                           整形栈的实现
//******************************************************************

//整形栈结构体
typedef struct {
    int* base;
    int* top;
    int size;
}intStack;


//栈初始化
intStack intStack_init()
{
    intStack s;
    s.base = (int*)malloc(sizeof(int) * STACK_INIT_SIZE);
    s.top = s.base;
    s.size = STACK_INIT_SIZE;
    return s;
}

//入栈
void intPush(intStack* s, int e)
{
    if (s->top - s->base >= s->size)
    {
        s->size += STACK_INCREMENT;
        s->base = (int*)realloc(s->base, sizeof(int) * s->size);
    }
    *s->top = e;
    s->top++;
}

//出栈
int intPop(intStack* s)
{
    if (s->top != s->base)
    {
        s->top--;
        return *s->top;
    }
    return -1;
}


//******************************************************************
//                         字符栈的实现
//******************************************************************

//字符栈结构体
typedef struct {
    char* base;
    char* top;
    int size;
}charStack;


//栈初始化
charStack charStack_init()
{
    charStack s;
    s.base = (char*)malloc(sizeof(char) * STACK_INIT_SIZE);
    s.top = s.base;
    s.size = STACK_INIT_SIZE;
    return s;
}

//入栈
void charPush(charStack* s, char e)
{
    if (s->top - s->base >= s->size)
    {
        s->size += STACK_INCREMENT;
        s->base = (char*)realloc(s->base, sizeof(char) * s->size);
    }
    *s->top = e;
    s->top++;
}

//出栈
char charPop(charStack* s)
{
    if (s->top != s->base)
    {
        s->top--;
        return *s->top;
    }
    return -1;
}

//得到栈顶元素，但不出栈
char getTop(charStack* s)
{
    s->top--;
    char temp = *s->top;
    s->top++;
    return temp;
}

//******************************************************************
//                      使用栈结构求解表达式
//******************************************************************

//得到操作符在数组prior中的索引值
int getIndex(char ope)
{
    switch (ope)
    {
    case '+': return 0;
    case '-': return 1;
    case '*': return 2;
    case '/': return 3;
    case '(': return 4;
    case ')': return 5;
    case '#': return 6;
    }
}

//求得两个操作数和一个操作符的运算结果
int compute(int operand1, int operand2, char ope)
{
    switch (ope)
    {
    case '+': return operand1 + operand2;
    case '-': return operand1 - operand2;
    case '*': return operand1 * operand2;
    case '/': return operand1 / operand2;
    }
}

//由表达式字符串指针，得到下一个操作符或操作数
//得到操作符标记key=0，得到操作数标记key=1
//返回偏移后的字符串指针
char* operand_or_operator(char* p, int* operand, char* ope, int* key)
{
    while (*p == ' ') p++;               //跳过空格
    if (*p >= '0' && *p <= '9')          //得到操作数
    {
        *operand = 0;
        int dec = 1;                    //十进制数位权重
        intStack s = intStack_init();   //使用整形栈转化数值        
        while (*p >= '0' && *p <= '9')   //操作数位由高到低依次压入栈中
        {
            intPush(&s, *p - '0');
            p++;
        }
        while (s.base != s.top)          //依次读取栈中操作数各位
        {
            *operand += intPop(&s) * dec;
            dec *= 10;
        }
        *key = 1;
    }
    else                               //得到操作符
    {
        switch (*p)
        {
        case '+':*ope = '+'; break;
        case '-':*ope = '-'; break;
        case '*':*ope = '*'; break;
        case '/':*ope = '/'; break;
        case '(':*ope = '('; break;
        case ')':*ope = ')'; break;
        case '#':*ope = '#'; break;
        }
        p++;
        *key = 0;
    }
    return p;
}

//由表达式字符串得到最终计算结果
int output(char* p)
{
    intStack operandStack = intStack_init();     //初始化操作数栈
    charStack operatorStack = charStack_init();  //初始化操作符栈
    charPush(&operatorStack, '#');
    int operand, key, index1, index2;
    char ope;
    while (operatorStack.base != operatorStack.top)  //操作符栈空代表计算结束
    {
        p = operand_or_operator(p, &operand, &ope, &key);
        if (key)  //得到操作数
            intPush(&operandStack, operand);
        else     //得到操作符
        {
            index1 = getIndex(getTop(&operatorStack));
            index2 = getIndex(ope);
            while (prior[index1][index2] == 2)   //top优先级高于c
            {
                intPush(&operandStack, compute(intPop(&operandStack), intPop(&operandStack), charPop(&operatorStack)));
                index1 = getIndex(getTop(&operatorStack));
            }
            if (prior[index1][index2] == 1)      //top优先级低于c
            {
                charPush(&operatorStack, ope);
            }
            else if (prior[index1][index2] == 0) //top优先级等于c
            {
                charPop(&operatorStack);
            }
            else
            {
                printf("Enter Error!!!\n");
                return 0XFFFFFFFF;
            }
        }
    }
    return intPop(&operandStack);
}

//******************************************************************
//                              主函数
//******************************************************************

void main()
{
    char str[100];
    int out;
    printf("以#结尾：\n");
    cin>> str;
    out = output(str);
    if (out != 0XFFFFFFFF)
        printf("结果等于：\n%d\n\n", out);
}