p2.c

一个表达式计算器的算法,编译后运行,输出output.txt

/* P2.c */

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

#define MAXLINE 80


int main()
{
	FILE *fi, *fo;
	char str[MAXLINE];
	double result;

	fi = fopen("input.txt", "r");
	fo = fopen("output.txt", "w");
	while (fgets(str, MAXLINE, fi))
	{
		DeleteBlanks(str);
		if (strlen(str) > 0 && str[strlen(str) - 1] == '\012')
		{
			str[strlen(str) - 1] = '\0';
		}
		if (Calculate(str, &result))
		{
			/* Success */
			fprintf(fo, "%.2lf\n", result);
		}
		else
		{
			fprintf(fo, "ERROR IN INFIX NOTATION\n");
		}
	}
	fclose(fi);
	fclose(fo);

	return 0;
}

/* Stack Functions. */
Stack* CreateStack(void)
{
	Stack* pStack;
	pStack = malloc(sizeof(Stack));
	if (pStack == NULL)
	{
		printf("Out of space!!!\n");
	}
	pStack->pNext = NULL;
	return pStack;
}

int IsEmpty(Stack *pStack)
{
	return pStack->pNext == NULL;
}

void ClearStack(Stack *pStack)
{
	Stack* pNode;
	if (!IsEmpty(pStack))
	{
		pNode = pStack;
		pStack = pStack->pNext;
		free(pNode);
	}
}

void Push(data elem, Stack *pStack)
{
	Stack* pNode;
	pNode = (Stack*)malloc(sizeof(Stack));
	if (pNode == NULL)
	{
		printf("Out of space!!!\n");
	}
	else
	{
		pNode->elem = elem;
		pNode->pNext = pStack->pNext;
		pStack->pNext = pNode;
	}
}

int Fetch(Stack *pStack, data *pData)
{
	if (IsEmpty(pStack))
	{
		printf("Empty stack!\n");
		return 0;
	}
	else
	{
		*pData = pStack->pNext->elem;
		return 1;
	}
}

int Pop(Stack *pStack, data *pData)
{
	Stack* pNode;
	if (IsEmpty(pStack))
	{
		printf("Empty stack!\n");
		return 0;
	}
	else
	{
		pNode = pStack->pNext;
		*pData = pNode->elem;
		pStack->pNext = pNode->pNext;
		free(pNode);
		return 1;
	}
}

/*--------------------------------------*/
/*   Convert Infix to Postfix.          */
/*   Return value:                      */
/*   0:		succeeded;                  */
/*   -1:	ERROR IN INFIX NOTATION;    */
/*--------------------------------------*/
//int ConvertInfixToPostfix(char *pExpression)
//{
//	;
//}

/*-------------------------------------------------*/
/*   Compare the two operators' precedence,        */
/*   exclude '(' and ')'.                          */
/*   Return value:                                 */
/*   0:		equal;                                 */
/*   1:		ch1 has the higher precedence;         */
/*   -1:	ch2 has the higher precedence;         */
/*   -2:	not valid operator;                    */
/*-------------------------------------------------*/
int CompareOperatorPrecedence(char ch1, char ch2)
{
	int rank1, rank2;		/* ('^'): rank = 1;   ('n' - negative sign, 'p' - positive sign): rank = 2;   ('*', '/', '%'): rank = 3;   ('+', '-'): rank = 4; */
	rank1 = rank2 = 0;
	if (IsOperator(ch1) && IsOperator(ch2))
	{
		switch(ch1)
		{
		case '^':
			rank1 = 1;
			break;
		case 'n':
		case 'p':
			rank1 = 2;
			break;
		case '*':
		case '/':
		case '%':
			rank1 = 3;
			break;
		case '+':
		case '-':
			rank1 = 4;
			break;
		default:
			break;
		}

		switch(ch2)
		{
		case '^':
			rank2 = 1;
			break;
		case 'n':
		case 'p':
			rank2 = 2;
			break;
		case '*':
		case '/':
		case '%':
			rank2 = 3;
			break;
		case '+':
		case '-':
			rank2 = 4;
			break;
		default:
			break;
		}
	}

	if (rank1 == 0 || rank2 == 0)
	{
		return -2;
	}
	else if (rank1 == rank2)
	{
		return 0;
	}
	else
	{
		return rank1 < rank2 ? 1 : -1;
	}
}

int IsDigitalChar(char ch)
{
	if (ch >= '0' && ch <= '9')
	{
		return 1;
	}
	else
	{
		return 0;
	}

}

/* Judge whether the char is an operator, exclude '(' and ')'. */
int IsOperator(char ch)
{
	if (ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '%' || ch == '^')
	{
		return 1;
	}
	else
	{
		return 0;
	}
}

/*-------------------------------------------------------------*/
/*   Calculate the expression.                                 */
/*   Parameter:                                                */
/*   [in] str:                                                 */
/*            Pointer to the expression to be calculated.      */
/*   [out] out_result:                                         */
/*            Pointer to the result of the expression.         */
/*   Return value:                                             */
/*   1:	   Succeeded;                                          */
/*   0:    ERROR IN INFIX NOTATION;                            */
/*-------------------------------------------------------------*/
int Calculate(char *str, double *out_result)	// recursive version Calculate2() ... ?? When encounters a '('
{
	int i;
	Stack *pOperandsStack, *pOperatorsStack;
	char chCurrent, chLast, chNext;
	double tmpOperand;
	char *ptrCur = str, *ptrTmp;
	data elem;
	char chTmp;

	atomCalcElems atomElems;
	data elemOperand1, elemOperand2;
	double result;

	pOperandsStack = CreateStack();
	pOperatorsStack = CreateStack();
	if (pOperandsStack == NULL || pOperatorsStack == NULL)
	{
		return 0; // Out of memory.
	}

	chLast = '\0';
	while ((chCurrent = *ptrCur) != '\0')
	{
		chNext = *(ptrCur+1);// ptrCur[0] ??
		switch(chCurrent)
		{
		case '-'://-(9-7) ???????
		case '+':
			if ((IsOperator(chLast) || chLast == '(' || chLast == '\0') && (IsDigitalChar(chNext) || chNext == '.' || chNext == '('))		// a positive or negative sign
			{
				chTmp = chCurrent == '-' ? 'n' : 'p';
			}
			else
			{
				/* Two sequential operators, a ')' directly after an operator, or an operator as the terminal is forbidden. */
				if (IsOperator(chNext) || chNext == ')' || chNext == '\0')
				{
					if (chNext == '+' || chNext == '-')
					{
						chTmp = *(ptrCur+2);
						if (!IsDigitalChar(chNext) && chNext != '.' && chNext != '(')
						{
							return 0;			// ERROR IN INFIX NOTATION
						}
					}
					else
					{
						return 0;						// ERROR IN INFIX NOTATION
					}
				}
				chTmp = chCurrent;
			}
			PushOperatorWithProcess(chTmp, pOperatorsStack, pOperandsStack);
			break;
		case '%':						/* the left and right operands must be integers */
			/* check left side */
			ptrTmp = ptrCur;
			while (--ptrTmp >= str && (chTmp = *ptrTmp) != '(')
			{
				if (chTmp == ')')
				{
					i = 1;										/* use i to count the pairs of parentheses */
					while (--ptrTmp >= str)							// 0x00000000 - 1 ???
					{
						chTmp = *ptrTmp;
						if (chTmp == ')')
						{
							i++;
						}
						else if (chTmp == '(')
						{
							if (--i == 0)
							{
								break;
							}
						}
						else
						{
							if (chTmp == '.' || chTmp == 'e' || chTmp == 'E' || chTmp == '^')
							{
								return 0;	// ERROR IN INFIX NOTATION ( '%' : illegal, left operand has type 'double' )
							}
						}
					}
					if (i > 0)
					{
						return 0;	// ERROR IN INFIX NOTATION
					}
				}
				else if (IsOperator(chTmp))
				{
					if ((chTmp == '+' || chTmp == '-') && ((ptrTmp - 1 >= str && IsOperator(*(ptrTmp - 1))) || chLast == '\0'))			// a positive or negative sign
					{
						continue;
					}
					else if (chTmp == '^')
					{
						return 0;	// ERROR IN INFIX NOTATION ( '%' : illegal, left operand has type 'double' )
					}
					else
					{
						if (CompareOperatorPrecedence(chTmp, '%') == -1)			/* '%' has the higher precedence */
						{
							break;
						}
					}
				}
				else
				{
					if (chTmp == '.' || chTmp == 'e' || chTmp == 'E'/* || chTmp == '^'*/)
					{
						return 0;	// ERROR IN INFIX NOTATION ( '%' : illegal, left operand has type 'double' )
					}
				}
			}
			/* check right side */
			ptrTmp = ptrCur;
			while ((chTmp = *++ptrTmp) != '\0' && chTmp != ')')
			{
				if (chTmp == '(')
				{
					i = 1;										/* use i to count the pairs of parentheses */
					while (*++ptrTmp != '\0')							// 0xFFFFFFFF - 1 ???
					{
						chTmp = *ptrTmp;
						if (chTmp == '(')
						{
							i++;
						}
						else if (chTmp == ')')
						{
							if (--i == 0)
							{
								break;
							}
						}
						else
						{
							if (chTmp == '.' || chTmp == 'e' || chTmp == 'E' || chTmp == '^')
							{
								return 0;	// ERROR IN INFIX NOTATION ( '%' : illegal, right operand has type 'double' )
							}
						}
					}
					if (i > 0)
					{
						return 0;	// ERROR IN INFIX NOTATION
					}
				}
				else if (IsOperator(chTmp))
				{
					if ((chTmp == '+' || chTmp == '-') && ((*(ptrTmp + 1) != '\0' && IsOperator(*(ptrTmp + 1))) || chLast == '\0'))			// a positive or negative sign
					{
						continue;
					}
					else if (chTmp == '^')
					{
						return 0;	// ERROR IN INFIX NOTATION ( '%' : illegal, right operand has type 'double' )
					}
					else
					{
						if (CompareOperatorPrecedence(chTmp, '%') == -1)			/* '%' has the higher precedence */
						{
							break;
						}
					}
				}
				else
				{
					if (chTmp == '.' || chTmp == 'e' || chTmp == 'E'/* || chTmp == '^'*/)
					{
						return 0;	// ERROR IN INFIX NOTATION ( '%' : illegal, left operand has type 'double' )
					}
				}
			}
			/* Two sequential operators, a ')' directly after an operator, or an operator as the terminal is forbidden. */
			if (IsOperator(chNext) || chNext == ')' || chNext == '\0')
			{
				if (chNext == '+' || chNext == '-')
				{
					chTmp = *(ptrCur+2);
					if (!IsDigitalChar(chNext) && chNext != '.' && chNext != '(')
					{
						return 0;			// ERROR IN INFIX NOTATION
					}
				}
				else
				{
					return 0;						// ERROR IN INFIX NOTATION
				}
			}
			chTmp = chCurrent;
			// Push(elem, pOperatorsStack);
			PushOperatorWithProcess(chTmp, pOperatorsStack, pOperandsStack);
			break;
		case '*':
		case '/':
		case '^':
		case '(':
			/* Two sequential operators, a ')' directly after an operator, or an operator as the terminal is forbidden. */
			/* The same as the format of sequential "()" and an operator after a '('.                                   */
			if (IsOperator(chNext) || chNext == ')' || chNext == '\0')
			{
				if (chNext == '+' || chNext == '-')
				{
					chTmp = *(ptrCur+2);
					if (!IsDigitalChar(chNext) && chNext != '.' && chNext != '(')
					{
						return 0;			// ERROR IN INFIX NOTATION