#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define STACK_INIT_SIZE 100
#define STACK_INCREAMENT 10
#pragma warning(disable:4996)//我用的vs2015，不加这句用scanf会报错（使用了unsafe的函数）

typedef struct { //栈
    char *base;
    char *top;
    int stackSize;
} Stack;

void initStack(Stack &stack) { //初始化栈
    stack.base = stack.top = (char *)malloc(sizeof(char) * STACK_INIT_SIZE);
    stack.stackSize = STACK_INIT_SIZE;
}
void push(Stack &S, char p) { //入栈
    if (S.top - S.base >= S.stackSize)
    {
        S.base = (char*)realloc(S.base, (S.stackSize + STACK_INCREAMENT)*sizeof(char));
        S.top = S.stackSize + S.base;
        S.stackSize += STACK_INCREAMENT;
    }
    *S.top++ = p;
}
void pop(Stack &stack, char &p) { //出栈
    if (stack.base == stack.top)
    {
        p = NULL; return;
    }
    p = *--stack.top;
}
char getTop(Stack stack) { //获得栈顶元素
    if (stack.base == stack.top) return NULL;
    return *(stack.top - 1);
}

char *NIBOLAN(char *e) /* 返回表达式e的逆波兰式 */
{//栈s1用于存放运算符，栈s2用于存放逆波兰式
    Stack s1, s2;initStack(s1);initStack(s2);
    push(s1, ‘#‘);
    //假设字符‘#‘是运算级别最低的运算符，并压入栈s1中
    //p指针用于遍历传入的字符串，ch用于临时存放字符,length用于计算字符串长度 
    char *p = e, ch;int length = 0;
    for (; *p != ‘\0‘; p++)//逐个字符访问
    {
        switch (*p)
        {
            //遇‘(‘则直接入栈s1
            //遇‘)‘则将距离栈s1栈顶的最近的‘(‘之间的运算符，逐个出栈，依次送入栈s2,此时抛弃‘(‘
        case ‘(‘:push(s1, *p); break;
        case ‘)‘:while (getTop(s1) != ‘(‘)
                { 
                    pop(s1, ch);
                    push(s2, ch); 
                }pop(s1, ch); break;
            //遇下列运算符，则分情况讨论：
            //1.若当前栈s1的栈顶元素是‘(‘，则当前运算符直接压入栈s1；
            //2.否则，将当前运算符与栈s1的栈顶元素比较，若优先级较栈顶元素大，则直接压入栈s1中,
            //  否则将s1栈顶元素弹出，并压入栈s2中，直到栈顶运算符的优先级别低于当前运算符，然后再将当前运算符压入栈s1中
        case ‘+‘:
        case ‘-‘:
            for (ch = getTop(s1); ch != ‘#‘; ch = getTop(s1))
            {
                if (ch == ‘(‘) break;
                else pop(s1, ch); push(s2, ch);
            }push(s1, *p); length++; break;
        case ‘*‘:
        case ‘/‘:
            for (ch = getTop(s1); ch != ‘#‘&&ch != ‘+‘&&ch != ‘-‘; ch = getTop(s1))
            {
                if (ch == ‘(‘) break;
                else pop(s1, ch); push(s2, ch);
            }push(s1, *p); length++; break;
        default:
            push(s2, *p); length++;
        }
    }
//若栈s1非空，则将栈中元素依次弹出并压入栈s2中
    while (s1.base!=s1.top && getTop(s1) != ‘#‘)
    {
         pop(s1, ch);
         push(s2, ch);
   }
 //最后将栈s2输出，逆序排列成字符串;
    char *result;
    result = (char *)malloc(sizeof(char)*(length + 1));
    result += length;
    * result = ‘\0‘;
    result--;
    for (; s2.base!=s2.top; result--)
    {
        pop(s2, ch);
        * result = ch;
     }
    ++result;
     return result;
 }
void main() 
{
    while (1)
    {
        char str[100];
        int i;
        for (i = 0; i<100; i++)str[i]= ‘\0‘;
        printf("请输入表达式：\n");
        scanf("%s",str);
        printf("%s", NIBOLAN(str));
    }
}