[application of stack] - infix expression to suffix expression

Problem description ：

How to convert infix expression to suffix expression , First of all, let's look at the connections and differences between them ：

• Infix expression （ Or infix notation ） It's a general expression of arithmetic or logic formula , Operators are in the middle of operands in the form of infixes （ example ：3 + 4）, Infix expression is a common arithmetic expression .
• however , This expression is inconvenient for computers to do calculations , therefore , Suffix expression ：
  An expression E The suffix form of can be defined as follows ：
  （1） If E Is a variable or constant , be E The suffix of is E In itself .
  （2） If E yes E1 op E2 Expression of form , here op Is any binary operator , be E The suffix of is E1’ E2’ op, here E1’ and E2’ Respectively E1 and E2 Postfix of .
  （3) If E yes （E1） Expression of form , be E1 The suffix of E Postfix of .
  Such as ： We usually write a+b, This is infix expression , As a suffix expression ：ab+

---

Cause analysis ：

We can easily find out how to convert infix expression to suffix expression , But how to implement it with stack ？
It mainly deals with the following special situations ：

---

Code implementation ：

#ifndef __STACK_H
#define __STACK_H

typedef char ElemType;

typedef  struct Stack
{
    
	ElemType   *stack_low;
	int          top;
	int          size;
}Stack;

void InitStack(Stack *st,  int init_size);

bool  Empty(Stack *st);

bool  Push(Stack *st, ElemType value);

bool  Pop(Stack *st);

bool Top(Stack *st, ElemType *reval);

void DestroyStack(Stack *st);

#include "stack.h"
#include <string.h>
#include<stdio.h>
#include <stdlib.h>
#include<ctype.h>

static bool Full(Stack *st)
{
    
	return st->top == st->size;
}

static bool AppendSpace(Stack *st)
{
    
	ElemType *new_space = (ElemType*)malloc(sizeof(ElemType) * st->size * 2);
	if(new_space == NULL) return false;

	for(int i = 0; i < st->size; ++i)
	{
    
		new_space[i] = st->stack_low[i];
	}

	free(st->stack_low);
	st->stack_low = new_space;
	st->size *= 2;

	return true;
}

void InitStack(Stack *st, int init_size)
{
    
	if(st == NULL)  exit(0);

	init_size = init_size > 0 ? init_size : 10;

	st->stack_low =  (ElemType*)malloc(sizeof(ElemType) * init_size);
	if(st->stack_low == NULL)  exit(0);

	st->top = 0;
	st->size = init_size;
}

bool  Empty(Stack *st)
{
    
	if(st == NULL) exit(0);

	return st->top == 0;
}

bool  Push(Stack *st, ElemType value)
{
    
	if(st == NULL) exit(0);

	if(Full(st))
	{
    
		if(!AppendSpace(st))
		{
    
			return false;
		}
	}

	st->stack_low[st->top++] = value;
	return true;
}
bool  Pop(Stack *st)
{
    
	if(st == NULL)  exit(0);

	if(Empty(st)) return false;

	st->top--;
	return true;
}
bool Top(Stack *st, ElemType *reval)
{
    
	if(st == NULL) exit(0);

	if(Empty(st)) return false;

	*reval = st->stack_low[st->top - 1];
	return true;
}
void DestroyStack(Stack *st)
{
    
	if(st == NULL) exit(0);

	free(st->stack_low);
	st->stack_low = NULL;
	st->top = st->size  = 0;
}

// Infix to suffix 
void InfixToSuffix(char *str)
{
    
	if(str==NULL) return;
	Stack s;
	InitStack(&s,10);

	int i=0; // Start traversing the subscript of the expression string 

	while(str[i]!='\0')
	{
    
		if(str[i]==' ')
		{
    
			i++;
			continue;
		}
		if(isdigit(str[i])) // In case of numbers 
		{
    
			printf("%c",str[i]);
			if(!isdigit(str[i+1])) 
			{
    
				printf(" ");
			}
		}
		else if(str[i]=='(') // If it is the case of the left bracket 
		{
    
			Push(&s,str[i]);
		}
		else if(str[i]==')') // If it is the case of the right parenthesis 
		{
    
			int flag=0;
			while(!Empty(&s))
			{
    
				ElemType val;
				Top(&s,&val);
				Pop(&s);

				if(val=='(')
				{
    
					flag=1;
					break;
				}

				printf("%c ",val);
			}

			if(!flag)
			{
    
				printf(" Bracket mismatch \n");
			}

		}
		else if(str[i]=='*' || str[i]=='/')
		{
    
			ElemType val;
			while(!Empty(&s))
			{
    
				Top(&s,&val);
				if(val=='(' || 
					val=='+' || 
					val=='-')  break;
				Pop(&s);
				printf("%c ",val);
			}
			Push(&s,str[i]);
		}
		else if(str[i]=='+' || str[i]=='-')
		{
    
			ElemType val;
			while(!Empty(&s))
			{
    
				Top(&s,&val);
				if(val=='(' ) break;
				Pop(&s);
				printf("%c ",val);
			}
			Push(&s,str[i]);
		}
		else 
		{
    
			printf(" Incorrect input ！\n");
			return;
		}

		i++;
	}

	while(!ElemType(&s))
	{
    
		ElemType val;
		Top(&s,&val);
		printf("%c ",val);
		Pop(&s);
	}
	printf("\n");

	DestroyStack(&s);
}

int main()
{
    
	char str[]="12*4+34/5-(56+67*4)+32";
	printf("\n");
	InfixToSuffix(str);
	return 0;
}