数据结构 栈的应用 逆波兰表达式

      #include <stdio.h>
      #include <stdlib.h>
      #define STACT_INIT_SIZE 100
      #define STACTINCREMENT 10
      #define OK 1
      #define ERROR 0
      #define OVERFLOW -2
      typedef char SElemType;
      typedef struct
      {
      	SElemType *base;
      	SElemType *top;
     	int stacksize;
      }SqStack;
      int InitStack(SqStack &S)
      {
      	S.base = (SElemType *)malloc(STACT_INIT_SIZE * sizeof(SElemType));
     	if (!S.base)
      	{
     		exit(OVERFLOW);
      	}
      	S.top = S.base ;
      	S.stacksize = STACT_INIT_SIZE;
     	return OK;
      }
      int Push(SqStack &S, SElemType e)
      {
     	if (S.top - S.base >= S.stacksize)
      	{
      		S.base = (SElemType*)realloc(S.base , (S.stacksize + STACTINCREMENT) * sizeof(SElemType));
     		if (!S.base)
      		{
     			exit(OVERFLOW);
      		}
      		S.top = S.base + S.stacksize ;
      		S.stacksize += STACTINCREMENT;
      	}
      	*S.top++ = e;
     	return OK;
      }
      int Pop(SqStack &S, SElemType &e)
      {
     	if (S.base == S.top)
      	{
     		return ERROR;
      	}
      	e = *--S.top;
     	return OK;
      }
      int GetTop(SqStack S)
      {
     	if (S.base == S.top)
      	{
     		return ERROR;
      	}
     	return *(S.top-1);
      }
      int StackEmpty(SqStack S)
      {
     	if (S.top == S.base )
      	{
     		return 1;
      	}
     	return 0;
      }
      int DestroyStack(SqStack &S)
      {
     	free(S.base);
      	S.base = NULL;
      	S.top = NULL;
      	S.stacksize = 0;
     	return OK;
      }
      char *RPExpression(char *e)
      {/*设置两个栈，s1用来存储操作符,s2用来存储数值和从s1弹出来的操作符,即逆波兰表达式*/
      	SqStack s1,s2;
      	InitStack(s1);
      	InitStack(s2);
      	Push(s1, '#');/*假设字符'#'是运算级别最低的运算符，并压入栈s1中*/
     	char *p = e, ch;
     	int length = 0;
     	for (; *p != '\0'; p++)
      	{
     		switch (*p)
      		{
     		case '('://遇'('则直接入栈s1
      			Push(s1,*p);
     			break;
     		case ')':
     			//遇')'则将距离栈s1栈顶的最近的'('之间的运算符，逐个出栈，依次送入栈s2,此时抛弃'('
     			while (GetTop(s1) != '(')
      			{
       Pop(s1,ch);
       Push(s2,ch);
      			}
      			Pop(s1,ch);//将s1里面的(抛弃
     			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;
      //遇操作数则直接压入栈s2中
     		default:
      			Push(s2,*p);
      			length++;
      		}
      	}
     	//若栈s1非空，则将栈中元素依次弹出并压入栈s2中
     	while (!StackEmpty(s1) && GetTop(s1) != '#')
      	{
      		Pop(s1,ch);
      		Push(s2,ch);
      	}
     	//最后将栈s2输出，逆序排列成字符串;
     	char *result;
      	result = (char *)malloc(sizeof(char)*(length+1));
      	result += length;
      	*result = '\0';
      	result--;
     	for (;!StackEmpty(s2); result--)
      	{
      		Pop(s2,ch);
      		*result = ch;
      	}
      	++result;
      	DestroyStack(s1);
      	DestroyStack(s2);
     	return result;
      }
      int main()
      {
     	char str[10000];
     	scanf("%s",str);
     	printf("%s\n",RPExpression(str));
     	return 0;
      }
  
 

文章来源: blog.csdn.net，作者：悦来客栈的老板，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/qq523176585/article/details/17249133