四则运算的实现

继续温习数据结构...

实现用到了两个栈：操作数栈与操作符栈。

主要过程是将中序表达式转换为后续表达式，然后按顺序进行运算。

简单过程：1+8-7(中序) ---->18 7 - + （后序）--->11 + （运算8-7）---> 2 （运算1+1）

源码:

#include "stack.h"           //利用到了前一篇文章实现的栈
#define SIZE 256
#define PSIZE 512

char postOrder[SIZE];
Stack<char> s(SIZE);
Stack<int> res(SIZE);

int prior(char ch)    //自定义优先级
{
	if(ch=='+'||ch=='-')return 2;
	else if(ch=='*'||ch=='/')return 3;
	else if(ch=='('||ch==')')return 4;
	else if(ch=='=')return 1;
	else return 0;
}


int comp(int i,int j,char c)      //运算
{
	switch(c)
	{
	case '+':
		return i+j;
	case '-':
		return i-j;
	case '*':
		return i*j;
	case '/':
		return i/j;
	default:
		return -1;
	}
}

int compute()
{
	for(int i=0;i!=strlen(postOrder);)
	{
		if (postOrder[i]==' '||postOrder[i]==NULL||postOrder[i]=='=')
		{
			++i;
			continue;
		}   
		if (postOrder[i]>='0'&&postOrder[i]<='9'/*&&!res.isFull()*/)
		{ 
			int val=0;                               //计算操作数的大小
			while(postOrder[i]>='0'&&postOrder[i]<='9')
			{
				val=10*val+(postOrder[i]-'0');
				i++;
			}
			res.push(val);
			continue;
		}
		if(res.top>=1)
		{
			int p=res.pop();         //取出离第一个操作符最近的两个操作数
			int q=res.pop();
			int s1=comp(q,p,postOrder[i]);    //进行四则运算
			res.push(s1);
			++i;
		}
	}
	return res.pop();
}

void change(char *prestr)
{
	int i=0,j=0;
	while(i<SIZE)
	{
		if (prestr[i]==' '||prestr[i]==NULL)
		{i++;continue;}
		if(prestr[i]>='0'&&prestr[i]<='9')         //将字符串转换为表示后续表达式的字符数组
		{
			while(prestr[i]>='0'&&prestr[i]<='9')
			{                                    //如果当前字符为数字，则继续
				postOrder[j++]=prestr[i++];
			}
			postOrder[j++]=' ';
		}
		if(prestr[i]==')')        //如果为右括号，则进行出栈操作，直到遇到左括号为止
		{
			int flag = 0;
			while(!s.isEmpty())
			{
				if(s.data[s.top]=='(')
				{
					flag=1;
					++i;
					s.pop();
					break;
				}
				postOrder[j++]=s.pop();
				postOrder[j++]=' ';
			}
			if(s.isEmpty()&&flag==0)
			{
				cout<<"Error:Do you miss a '('?"<<endl;
				exit(0);
			}
		}
		if(prestr[i]!=')'&&!s.isFull()&&(s.isEmpty()   //如果当前符号优先级大于栈顶符号优先级，则入栈
			||prior(prestr[i])>prior(s.data[s.top])))
		{
			s.push(prestr[i++]);
		}
		else if(prestr[i]!=')')
		{
			while(!s.isEmpty()&&prior(prestr[i])<=prior(s.data[s.top])
				&&s.data[s.top]!='(')             //如果当前符号优先级比栈顶的小，则出栈，直到栈顶符号优先级
			{                                     //小于等于当前符号优先级，然后入栈
				postOrder[j++]=s.pop(); //记录出栈的元素
				postOrder[j++]=' ';
			}
			s.push(prestr[i++]);
		}
	}
	while(!s.isEmpty())         //遍历完字符串后，将还未出栈的元素全部出栈，记录在后续表达式的后面
	{
		if(s.data[s.top]=='(')
		{
			cout<<"Error:Do you miss a ')'?"<<endl;
			exit(0);
		}
		postOrder[j++]=s.pop();
		postOrder[j++]=' ';
	}
}

int main()
{
	char preStr[PSIZE];
    char ch;
	int preIndex=0;
	memset(preStr,NULL,sizeof(preStr));

	for(int i=0;i<PSIZE;++i)
	{

		ch=getchar();
		if (ch==' '||ch==NULL)continue;
		if(ch=='/n')break;
		preStr[preIndex++]=ch;
		if(ch=='=')break;
	}

	if(strlen(preStr)>SIZE)
	{
		cout<<"Exception:/nThe size of expression is beyond default value."
			<<"/nThe length of a string cannot be larger than "<<SIZE<<"./n";
		exit(0);
	}
    change(preStr);
	for(int i=0;i<strlen(postOrder);++i)
	{
		cout<<postOrder[i];
	}
    cout<<endl;
	for(int i=0;i!=strlen(preStr);++i)
	{
		cout<<preStr[i];
	}
    cout<<endl<<compute()<<endl;
	return 0;
}