【データ構造】逆ポーランド表現法（RPN）：中綴り表現の拡張式

スタックを利用して実現される。

/*****************************************  
Copyright (c) 2015 Jingshuang Hu  
  
@filename:demo.c  
@datetime:2015.10.08  
@author:HJS  
@e-mail:[email protected]  
@blog:http://blog.csdn.net/hujingshuang  
*****************************************/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/***********************************************/
#define MAX_LENGTH 20
/***********************************************/
typedef struct
{
	char data[MAX_LENGTH];
	int top;
}SqStack;
/***********************************************/
int Express_Error(char *p);//      
SqStack Infix_suffix(char *p);//     
char Symbol_Priority(char ch);//   
int calc_suffix(SqStack p);//       
char calc_two(char p1, char p2, char symbol);//           
void change(char *p);//    
void Stack_Init(SqStack *p);//    
void Stack_Push(SqStack *p, char value);//  
char Stack_Pop(SqStack *p);//  
char Stack_Top(SqStack p);//     
int Stack_Length(SqStack p);//  
int Stack_Empty(SqStack p);//  
void Stack_ShowAll(SqStack p);//      
void Stack_Clear(SqStack *p);//   
/***********************************************/
//8+(3+5-2)*2					= 20
//7+(6-1)*2+9/3					= 20
//((20/5-3)+4)*2/5				= 2
//((30-10/2)+5)/10*2/3-1		= 1
//(3+2*(12+4)/4-2)/3+2			= 5
int main()
{
	int choise = 0;
	char str[MAX_LENGTH];
	SqStack s;
	while(1)
	{
		printf("     :");

		gets(str);
		if (Express_Error(str))//      ，    
		{
			printf("      ，     !
");
			continue;
		}
		change(str);//            
		s = Infix_suffix(str);//     
		printf("     :");
		puts(s.data);
		printf("  :%d", calc_suffix(s));
		getchar();getchar();
		system("cls");
	}
	return 0;
}
/***********************************************/
void change(char *p)//    
{
	int i = 0, j = 0, sum = 0;
	char *s = p;
	while(p[i] != '\0')
	{
		if ((p[i] >= '0') && (p[i] <= '9'))
		{
			sum = sum * 10 + p[i] - '0';
			if ((p[i + 1] > '9') || (p[i + 1] < '0'))
			{
				s[j] = sum + '0';
				sum = 0;
				j++;
			}
		}
		else
		{
			s[j] = p[i];
			j++;
		}
		i++;
	}
	s[j] = '\0';
	p = s;
}
/***********************************************/
SqStack Infix_suffix(char *p)//     
{
	char i = 0, pt = 0, pc = 0;//      、     
	char st = 0, sc = 0;//     、    
	SqStack s;//    、   、      
	SqStack s1;
	SqStack s2;
	Stack_Init(&s);
	Stack_Init(&s1);
	Stack_Init(&s2);
	//
	while(p[i] != '\0')
	{
		if ((p[i] != '+') && (p[i] != '-') && (p[i] != '*') && (p[i] != '/') \
			&& (p[i] != '%') && (p[i] !='(') && (p[i] != ')'))//       s2
		{
			Stack_Push(&s2, p[i]);
		}
		else//    s1，      s（s s1  ）
		{
			pc = Symbol_Priority(p[i]);//        
			if (Stack_Empty(s1) || ('(' == p[i]))//s1   '('     
			{
				Stack_Push(&s, pc);//     
				Stack_Push(&s1, p[i]);//    
			}
			else
			{
				pt = Stack_Top(s);//      
				st = Stack_Top(s1);//     
				if (')' == p[i])
				{
					while(st != '(')
					{
						Stack_Pop(&s);//   s  
						Stack_Push(&s2, Stack_Pop(&s1));//    s1，    s2
						st = Stack_Top(s1);
					}
					Stack_Pop(&s);// '('      
					Stack_Pop(&s1);// '('  
				}
				else//           
				{
					if (pc > pt)//   ：    >    ，    
					{
						Stack_Push(&s, pc);//     
						Stack_Push(&s1, p[i]);//    
					}
					else//   ：    <=    ，  ，       '('，    
					{
						while((!Stack_Empty(s1)) && (Stack_Top(s1) != '(') && (Stack_Top(s) >= pc))
						{
							Stack_Push(&s2, Stack_Pop(&s1));
							Stack_Pop(&s);
						}
						Stack_Push(&s1, p[i]);
						Stack_Push(&s, pc);
					}
				}
			}
		}
		i++;
	}
	while(!Stack_Empty(s1))// s1       ，    s2
	{
		Stack_Push(&s2, Stack_Pop(&s1));
		Stack_Pop(&s);
	}
	Stack_Push(&s2, '\0');//  '\0'，     
	return s2;
}
/***********************************************/
int calc_suffix(SqStack p)//       
{
	int i = 0;
	char *str = p.data;
	char p1, p2;
	SqStack s;
	Stack_Init(&s);
	while(str[i] != '\0')
	{
		if ((str[i] != '+') && (str[i] != '-') && (str[i] != '*') && (str[i] != '/') && (str[i] != '%'))//          
		{
			Stack_Push(&s, str[i]);
		}
		else//     ，           
		{
			p2 = Stack_Pop(&s);
			p1 = Stack_Pop(&s);
			Stack_Push(&s, calc_two(p1, p2, str[i]));
		}
		i++;
	}
//	Stack_Push(&s, '\0');
	return (Stack_Pop(&s) - '0');//           ，    
}
/***********************************************/
char calc_two(char p1, char p2, char symbol)//           
{
	char res = 0;
	switch(symbol)
	{
		case '+':
			res = (p1 - '0') + (p2 - '0');
			break;
		case '-':
			res = (p1 - '0') - (p2 - '0');
			break;
		case '*':
			res = (p1 - '0') * (p2 - '0');
			break;
		case '/':
			res = (p1 - '0') / (p2 - '0');
			break;
		case '%':
			res = (p1 - '0') % (p2 - '0');
			break;
		default:
			break;
	}
	return (res + '0');
}
/***********************************************/
int Express_Error(char *p)//      
{
	int i = 0, flag = 0;
	while((p[i] != '\0') && (flag == 0))
	{
		if (((p[i] >= '0') && (p[i] <= '9')) || ('+' == p[i]) || ('-' == p[i]) \
			|| ('*' == p[i]) || ('/' == p[i]) || ('(' == p[i]) || (')' == p[i]))
		{
			flag = 0;
		}
		else
		{
			flag = 1;
		}
		i++;
	}
	return flag;
}
/***********************************************/
char Symbol_Priority(char ch)//   
{
	if (('+' == ch) || ('-' == ch))
	{
		return 0;
	}
	else if (('*' == ch) || ('/' == ch) || ('%' == ch))
	{
		return 1;
	}
	else if (('(' == ch) || (')' == ch))
	{
		return 2;
	}
	else
	{
		return 3;//    
	}
}
/***********************************************/
void Stack_Init(SqStack *p)//    
{
	p->top = -1;
}
/***********************************************/
void Stack_Push(SqStack *p, char value)//  
{
	p->top++;
	p->data[p->top] = value;
}
/***********************************************/
char Stack_Pop(SqStack *p)//  
{
	return p->data[p->top--];
}
/***********************************************/
char Stack_Top(SqStack p)//  
{
	return p.data[p.top];
}
/***********************************************/
int Stack_Length(SqStack p)//  
{
	return p.top;
}
/***********************************************/
int Stack_Empty(SqStack p)//1   0  
{
	return (p.top <= -1) ? 1 : 0;
}
/***********************************************/
void Stack_ShowAll(SqStack p)//      
{
	char ch;
	while(!Stack_Empty(p))
	{
		ch = Stack_Pop(&p);
		printf("%c", ch);
	}
	printf("
");
}
/***********************************************/
void Stack_Clear(SqStack *p)//   
{
	p->top = -1;
}