완전한 역폴란드식 값 구하기

3836 단어
여기에 제가 창고를 하나 썼는데 사실 본질적으로 제가 쓴 창고는 STL이 가지고 있는 창고보다 효율이 높습니다.그리고 입력한 int를 Sstring으로 저장합니다.
안에 두 개의 귀속이 있는데 하나는 출점 과정에서 창고의 연산자의 우선순위에 따라 출점 여부를 판단하는 것이다. 하나는 역폴란드 표현식을 구한 후에 귀속 값을 구하는 것이다. 매번 한 번 연산한 후에 int수조는 앞으로 두 개를 이동한다.
``int numt = 0;
void PushSstring(Sstring &S, char c,bool isNum = false)
{
	if(S.index >= S.length - 1) 
	{
		S.base = (ElemType*)realloc(S.base,(S.length + STACKSIZE_INCREMENT)*sizeof(ElemType));
		S.length += STACKSIZE_INCREMENT;
	} 
	if(isNum){
		if(numt == 1) 
		{
			S.index++;
			S.base[S.index] = 0;
		}
//		cout << "S.base["<< S.index << "]:" << S.base[S.index] << " c:" << c << endl;
		S.base[S.index] = S.base[S.index]*10 + (int)c - 48;
//		cout << "   S.base["<< S.index << "]:" << S.base[S.index] << endl;
	}
	else {
//		cout << "c:" << c << " intc:" << (int)c << endl;
		S.index++;
		S.base[S.index] = -(int)c;
	}
}

Sstring TransformRPN(SqStack &S,char buffer[])
{
	int i = 0;
	Sstring rpn; InitSstring(rpn);
	while(buffer[i] != '\0')
	{
		char ch = buffer[i];
		int prior = GetPriority(ch);
		if (prior == 0){
			numt++;
			PushSstring(rpn,ch,true);
		}
		else {
			numt = 0;
			if (prior == 4)//GetPriority('(') = 4;
			{
				PushStack(S, ch);
			}
			else if (prior == 3)//GetPriority(')') = 3;
			{
				RecurvePop(S, ch, rpn);
				PopStack(S);
			}
			else {
				int topprior = GetPriority(*(S.top));
				 if (prior >= topprior){
					RecurvePop(S, ch, rpn);
				 }
				PushStack(S, ch);
			}
		}
		i++;
	}
	RecurvePop(S, '^', rpn);
	return rpn;
}

int CalculateRPN(Sstring &rpn)
{
	if(rpn.index == 1){
		return rpn.base[1];
	}
	int i = 1;
	while(rpn.base[i] >= 0)
	{
		i++;
	}
	char c = (char)(-rpn.base[i]); 
//	cout << rpn.base[i-2] <<  " " << c <<  " " << rpn.base[i-1] << endl;
	if(c == '+') rpn.base[i-2] += rpn.base[i-1];
	else if(c == '-') rpn.base[i-2] -= rpn.base[i-1];
	else if(c == '*') rpn.base[i-2] *= rpn.base[i-1];
	else if(c == '/') rpn.base[i-2] /= rpn.base[i-1];
	
	rpn.index -= 2;
	for(int j = i-1; j <= rpn.index; j++)
	{
		rpn.base[j] = rpn.base[j+2];
	}
	return CalculateRPN(rpn);
}

int main()
{
	SqStack S;
	if(InitStack(S) != OK) return 0;

	char buffer[10000];
	cin >> buffer;

	PushStack(S,'#');

	Sstring rpn = TransformRPN(S,buffer);
	//  , Int  
	
	//  
//	for(int i = 1; i <= rpn.index; i++)
//	{
//		if(rpn.base[i] < 0) cout << (char)(-rpn.base[i]) << " ";
//		else cout << rpn.base[i]<< " "; 
//	}
//	cout << endl;
	
	cout << CalculateRPN(rpn) << endl;
	
	return 0;
}

여기 앞에 코드예요.
#include 
#include 
#include 

#define STACK_INIT_SIZE 100
#define STACKSIZE_INCREMENT 10
#define SSTRING_INIT_SIZE 100
using namespace std;
typedef int ElemType;

typedef enum{
	OK = 1,
	ERROR = -1,
	TRUE = 2,
	FALSE = 3
}Status;

struct SqStack
{
	ElemType *base;
	ElemType *top;
	int stackSize;
};

struct Sstring{
	ElemType *base;
	int index;
	int length;
};

Status InitStack(SqStack &S)
{
	S.base = (ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));
	if(!S.base) return ERROR;
	S.top = S.base;
	S.stackSize = STACK_INIT_SIZE;
	return OK;
}

Status PushStack(SqStack &S,ElemType e)
{
	if(S.top - S.base >= S.stackSize) 
	{
		S.base = (ElemType*)realloc(S.base,(S.stackSize + STACKSIZE_INCREMENT)*sizeof(ElemType));
		S.stackSize += STACKSIZE_INCREMENT;
	}
//	cout < prior ) return;
	else {
		PushSstring(rpn,*(S.top));
		PopStack(S);
		RecurvePop(S, e, rpn);
	}
}

좋은 웹페이지 즐겨찾기