2-2.cpp

《数据结构-使用C语言》第三版

#include<stdio.h>
#include<malloc.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>

typedef char DataType;
#define MaxStackSize 100

#include"SeqStack.h"

char Operator[]="+-*/^();";
char  Priority[8][9]={
	{">><<<<>>"},{">><<<<>>"},{">>>><<>>"},{">>>><<>>"},
	{">>>>><>>"},{"<<<<<<= "},{">>>>> >>"},{"<<<<<< ="}};

int main()
{
	int i;
	SeqStack ExpMid, ExpAft;
	int ExpJudge(SeqStack *exp);
	int ExpChange(SeqStack *mid, SeqStack *aft);
	while(scanf("%s",ExpMid.stack)!=EOF)
	{
		StackInitiate(&ExpMid);
		StackInitiate(&ExpAft);

		ExpMid.top=strlen(ExpMid.stack);
		if(ExpJudge(&ExpMid)==0)continue;
		//printf("%s\n",ExpMid.stack);
		
		if(ExpChange(&ExpMid, &ExpAft)==0)continue;
		printf("Case:");
		for(i=0;i<ExpAft.top;i++)
			printf("%c",ExpAft.stack[i]);
		printf("\n\n");
	}
	return 0;
}

int ExpJudge(SeqStack *exp)
{
	int i,left,right,flag;
	char t;
 	
	left=0;
 	right=0;
 	flag=1;
 	for(i=0; i<exp->top; i++)
 	{
		t=exp->stack[i];
		if(t=='(')left++;
		else if(t==')')right++;
		else if(t=='+' || t=='-' || t=='*' || t=='/' || t=='^')
		{
			if(flag==1)
			{
				printf("error!\n\n");
				return 0;
			}
			flag=1;
		}
		else if((t>='0'&&t<='9') || (t>='a'&&t<='z') || (t>='A'&&t<='Z'))
		{
			if(flag==0)
			{
				printf("error!\n\n");
				return 0;
			}
			flag=0;
		}
		if(right>left)
		{
			printf("括号不匹配!\n\n");
			return 0;
		}
	}
	if(right!=left)
	{
		printf("括号不匹配!\n\n");
		return 0;
	}
	return 1;
}

char ConfirmPriority(char operator_1,char operator_2)
{//判断优先关系 
	int i,j;                                 //用来存储运算符优先关系在表中的下标
	i=strchr(Operator,operator_1)-Operator;  //查找运算符在字符串Operators中的相对位置
	j=strchr(Operator,operator_2)-Operator;
	return Priority[i][j];                   //返回运算符优先关系表中相应位置的"值" 
}		

int ExpChange(SeqStack *mid, SeqStack *aft)
{
	int i;
	DataType t,x1,x2;
	SeqStack temp;
	temp.stack[0]=';';
	temp.top=1;
	
	for(i=0;i<mid->top;i++)
	{
		x2=mid->stack[i];
		if((x2>='0'&&x2<='9') || (x2>='a'&&x2<='z') || (x2>='A'&&x2<='Z'))
		{
			if(StackPush(aft, x2)==0)return 0;
		}
		else if(x2=='+' || x2=='-' || x2=='*' || x2=='/' || x2=='^' || x2=='(' || x2==')' || x2==';')
		{
			if(StackTop(temp, &x1)==0)return 0;
			t=ConfirmPriority(x1,x2);
			if(t=='>')
			{
				do
				{
					if(StackPop(&temp,&x1)==0)return 0;
					if(StackPush(aft,x1)==0)return 0;
					
					if(StackTop(temp, &x1)==0)return 0;
					t=ConfirmPriority(x1,x2);
				}while(t=='>');
				
				/*if(t=='<')
				{if(StackPush(&temp,x2)==0)return 0;}
				else if(t=='=' && x1=='(' && x2==')')
				{if(StackPop(&temp,&x1)==0)return 0;}
				else if(t=='=' && x1==';' && x2==';')
				{break;}*/
			}
			if(t=='<')
			{if(StackPush(&temp,x2)==0)return 0;}
			else if(t=='=' && x1=='(' && x2==')')
			{if(StackPop(&temp,&x1)==0)return 0;}
			else if(t=='=' && x1==';' && x2==';')
			{break;}
		}
	}
	return 1;
}