111.cpp

输入一个运算字符串表达式

#include "iostream.h"
#include "stdlib.h"
#include "memory.h"
#include "afx.h"

enum stacktype
{
	stacktype_int,
	stacktype_char,
};


class QStack
{
public:
	QStack(stacktype type,int MaxSize)
	{
		switch(type) 
		{
		case stacktype_int:
			m_pDataList = (int*)malloc(MaxSize * sizeof(int));
			memset(m_pDataList, 0, MaxSize * sizeof(int));
			break;
		case stacktype_char:
			m_pDataList = (char*)malloc(MaxSize * sizeof(char));
			memset(m_pDataList, 0, MaxSize * sizeof(char));
			break;
		}
		m_CurSize = 0;
		m_nMaxSize = MaxSize;
		m_Type = type;
	}
	void pushback(void* p)
	{
		ASSERT(m_CurSize < m_nMaxSize);
		switch(m_Type)
		{
		case stacktype_int:
			*((int*)m_pDataList + m_CurSize++) = *(int*)p;
			break;
		case stacktype_char:
			*((char*)m_pDataList + m_CurSize++) = *(char*)p;
			break;
		}
	}
	void popback(void* p)
	{
		ASSERT(m_CurSize >= 1);
		switch(m_Type)
		{
		case stacktype_int:
			*(int*)p = *((int*)m_pDataList + m_CurSize - 1);
			break;
		case stacktype_char:
			*(char*)p = *((char*)m_pDataList + m_CurSize - 1);
			break;
		}
		m_CurSize--;
	}
	
	void GetDataList(void** ppList)
	{
		ASSERT(ppList);
		*ppList = NULL;
		if(m_CurSize == 0)
			return;
		switch(m_Type) 
		{
		case stacktype_int:
			*ppList = (int*)malloc(sizeof(int) * (m_CurSize + 1));
			memset(*ppList, 0, sizeof(int) * (m_CurSize + 1));
			memcpy(*ppList, m_pDataList, sizeof(int) * (m_CurSize + 1));
			break;
		case stacktype_char:
			*ppList = (char*)malloc(sizeof(char) * (m_CurSize + 1));
			memset(*ppList, 0, sizeof(char) * (m_CurSize + 1));
			memcpy(*ppList, m_pDataList, sizeof(char) * (m_CurSize + 1));
			break;
		}
	}

	void clear()
	{
		m_CurSize = 0;
	}

	bool IsEmpty()
	{
		if(m_CurSize == 0)
			return true;
		else
			return false;
	}
	int Size()
	{
		return m_CurSize;
	}
protected:
	int m_CurSize;
	void* m_pDataList;
	int m_nMaxSize;
	stacktype m_Type;
private:
};
static char Symbols[20] = 
{'+','-','*','/','=','(',')','\0'};
bool IsSymbol(char ch)
{
	char *p = Symbols;
	while(*p != 0) 
	{
		if(ch == *p)
		{
			return true;
		}
		p++;
	}
	return false;
}

bool CheckExpression(char *Formula)
{
	char *p = Formula;
	char *plast = NULL;
	int  markstack = 0;
	while(*p != 0)
	{
		if(IsSymbol(*p))
		{
			if(*p == '(')
				markstack++;
			else if(*p == ')')
				markstack--;
			if(markstack < 0)
				return false;
			//两个符号不能一起
			if(plast && IsSymbol(*plast))
			{
				//两个左括号可以在一起
				if(*plast == '(' && *p != '(')
					return false;
			}
			if(!plast && *p != '(')
				return false;
			//左括号地前面必须是符号或空
			if(plast && *p == '(' && !IsSymbol(*plast) && *plast != '(')
				return false;
			//右括号地后面必须是符号或空
			if(*(p + 1) && *p == ')' && !IsSymbol(*(p + 1)) && *(p + 1) != ')')
				return false;


		}
		else
		{
			if(plast && *plast == '=' )
				return false;
		}
		plast = p;
		p++;
	}
	if(markstack < 0)
		return false;
	if(plast && IsSymbol(*plast))
	{
		if(*plast != '=')
			return false;
	}
	return true;
}

void Trim(char *str, char** outstr)    //去掉字符串中的字符
{
	char* p = str;
	*outstr = (char*)malloc(strlen(str) + 1);
	memset(*outstr, 0, strlen(str) + 1);
	char* pout = *outstr;
	while (*p != 0) 
	{
		if(*p != ' ')
		{
			*pout = *p;
			pout++;
		}
		p++;
	}
}
int StrToInt(char *Str)
{
	int lastInt = 0;
	char *p = NULL;
	p = Str;
	while(*p != 0) 
	{
		lastInt = lastInt * 10 + (int)(*p - '0');
		p++;
	}
	return lastInt;
}

BOOL CompareSym(char a, char b)
{
	switch(a) 
	{
	case '*':
	case '/':
		if(b != '*' && b != '/')
			return TRUE;
		break;
	default:
		break;
	}
	return FALSE;
}

int Calc(int a, int b, char Sym)
{
	switch(Sym) 
	{
	case '+':
		return a + b;
		break;
	case '-':
		return a - b;
		break;
	case '*':
		return a * b;
	case '/':
		ASSERT(b);
		return a / b;
	default:
		break;
	}
	return 0;
}
void Clear(int* p, int size)
{
	int i;
	for(i = 0; i < size; i++)
	{
		*p++ = 0;
	}
}

void matching(char** ppstr, char* outstr)
{
	char* p = *ppstr + 1;
	int count = 1;
	int cpycount = 0;
	*outstr = (char)malloc(strlen(*ppstr) + 1);
	memset(outstr, 0, strlen(*ppstr) + 1);
	while (count > 0)
	{
		if(*p == '(')
		{
			count++;
			*(outstr + cpycount) = *p;
			p++;
		}
		else if(*p == ')')
		{
			count--;
			if(count == 0)
			{
				*ppstr = ++p;
				return;
			}
			*(outstr + cpycount) = *p;
			p++;
		}
		else
		{
			*(outstr + cpycount) = *p;
			p++;
		}
		cpycount++;
	}
}
int parse(char *Str)
{
	char* p = NULL; 
	Trim(Str, &p);
	QStack StackNum(stacktype_int, 100);
	QStack StackChr(stacktype_char, 100);
	QStack StackTemp(stacktype_char, 10);
	
	while(*p != 0)
	{
		if(!IsSymbol(*p))
		{
			char* plist;
			StackTemp.pushback(p);
			StackTemp.GetDataList((void**)&plist);
			if(plist)
			{
				int nVal = StrToInt(plist);
				if(*(p + 1) == 0)
				{
					StackNum.pushback(&nVal);
					StackTemp.clear();
				}
			}
		}
		else
		{
			char* plist;
			StackTemp.GetDataList((void**)&plist);
			if(plist)
			{
				int nVal = StrToInt(plist);
				StackNum.pushback(&nVal);
				StackTemp.clear();  //把字符变成数字，压入栈
			}
			if(*p == '(')
			{
				char cpystr[100];
				matching(&p, cpystr);
				int value = parse(cpystr);
				StackNum.pushback(&value);
				continue;
			}
			char chPop;
			if(!StackChr.IsEmpty())
			{
				StackChr.popback(&chPop);//弹出前一个符号，比较
				if(!CompareSym(*p, chPop))
				{
					char CurSym = *p;
					int nResult = 0;

					while(!CompareSym(CurSym, chPop))
					{
						int nNum1 = 0, nNum2 = 0;
						StackNum.popback(&nNum2);
						StackNum.popback(&nNum1);
						nResult = Calc(nNum1, nNum2, chPop);
						StackNum.pushback(&nResult);
						if(!StackChr.IsEmpty())
							StackChr.popback(&chPop);
						else
						{
							break;
						}
						if(CompareSym(CurSym, chPop))
						{
							StackChr.pushback(&chPop);
							StackChr.pushback(p);
						}
					}

					if(*p != '=')		
					{
						StackChr.pushback(p);
					}	
				}
				else
				{
					StackChr.pushback(&chPop);
					StackChr.pushback(p);
				}
			}
			else
				StackChr.pushback(p);
		}
		p++;
	}
	if(!StackChr.IsEmpty())
	{
		int nSize = 0;
		int StackSize = StackChr.Size();
		while (nSize < StackSize) 
		{
			int nNum1 = 0;
			int nNum2 = 0;
			char Sym;
			StackNum.popback(&nNum2);
			StackNum.popback(&nNum1);
			StackChr.popback(&Sym);
			int nVal = Calc(nNum1, nNum2, Sym);
			StackNum.pushback((void*)&nVal);
			nSize++;
		}
	}
	int nReVal = 0;
	StackNum.popback(&nReVal);
	ASSERT(StackNum.IsEmpty() && StackChr.IsEmpty());
	return nReVal;
}

void main()
{
	char str[100];
	cin>>str;
	int nValue = parse(str);
	cout<<nValue<<endl;
}

//(2+((3-6)*9))/5-8