expression.cpp

把中缀表达式转换为后缀表达后

#include "Expression.h"

Expression::Expression() {
	postfix="";
}
bool Expression::is_digit(char ch) {
	if(ch=='='||ch=='('||ch=='*'||ch=='/'||ch=='%'||ch=='+'||ch=='-'||ch==')')
		return false;
	return true;
}
int Expression::isp(char c)
{   //入栈后的优先级
    switch(c)
 {
      case '(':  return 1;
   case '*':  case '/':   case'%':  return 7;
   case '+':  case '-':   return 3;
   case ')':  return 8;
 }
 return 0;
}
int Expression::icp(char c)
{   //栈外的优先级
	switch(c)
	{  
	case '(':  return 8;
	case '*':  case '/':   case'%':  return 4;
	case '+': case '-':   return 2;
	case ')':  return 1;
	}
	return 0;
}

void Expression::infix_to_postfix(string infix)
{   //中缀转后缀 
	int i=0;
	Stack<char> operatorStack; 
	char ch='=',op,temp;
	operatorStack.push(ch);
	bool flag=false;
	while(!operatorStack.empty()&&infix[i]!='\0')
	{   
		if(is_digit(infix[i])) 
		{			
			if(!flag) postfix=postfix+infix[i];
			else
			{
                postfix=postfix+' ';
				postfix=postfix+infix[i];
			}
			flag=false;			
			i++;
		} 
		else 
		{
			flag=true;
			operatorStack.top(temp);
			if(isp(temp)<icp(infix[i]))
			{   
				operatorStack.push(infix[i]);  
				i++;
			}
		    else if(isp(temp)>icp(infix[i])) 
			{
				operatorStack.top(op); 
				operatorStack.pop();
				postfix=postfix+op;				
			}
			else 
			{
				operatorStack.top(op);
				operatorStack.pop();
				if(op=='(')   i++;
			}
		}
			
	}
	cout<<endl<<postfix<<endl;
}

double Expression::calculate_postfix()
{
	char ch;
	double value;
	for (int i=0;i<postfix.size();i++)
	{    
		ch = postfix[i];
		switch (ch)
		{
		case ' ' : break;	
		case '+' :
		case '-' :
		case '*' :
		case '/' :
			dispose_operator(ch);			
			break; 
		default :
			double temp=0;	
			while (ch>='0'&&ch<='9' )
			{				
				temp=10*temp+ch-'0';				
				ch=postfix[++i];	
				if(!is_digit(ch))	i--;				
			} 	
			theStack.push(temp);
			break;
		}
		
	}
	theStack.top(value);
    return value;
}
void Expression::dispose_operator(char ch)
{
	double num1;
	double num2;
	double value = 0;
	theStack.top(num2);
	theStack.pop( );
	theStack.top(num1);
	theStack.pop( );
	switch ( ch)
	{
	case '+' :
		value = num1 + num2;
		break;
	case '-' :
		value = num1 - num2;
		break;
	case '*' :
		value = num1 * num2;
		break;
	case '/' :
		value = num1 / num2;
		break;
	default :
		break;
	}
	theStack.push(value);
}