sufficalexpression.h

VC6.0环境下的多项式计算

#ifndef SUFFICALEXPRESSION_H
#define SUFFICALEXPRESSION_H


#include <iostream>
using namespace std ;

#include "stack.h"

/*  算法解释：
*      使用栈的算法也很多，说个好想的。假设表达式的字符来自输入流in，建立栈A存放运算符，
*      B存放结果，从in读入一个操作数压进B，读入一个运算符压进A，如此反复。 
*    1.读入一个元素e 
*    2.如果e是操作数或者(，压入B，跳转到1 
*    3.如果e是运算符(不包含括号)，跳转到3.1 
*    4.如果e是)，跳转到4.1 
*    5.如果e是EOF，即输入流结束，反复弹出A栈顶压入B，直到A为空，
*     算法结束，B从栈底到栈顶的符号即为后缀表达式 

  *    3.1.判断A的栈定符号char，如果char不为(，且优先级大于等于e，则弹出char压入B，跳转到4，
  *    如果char为空，即栈中为空，或其他情况直接把e压入A，跳转到1 
  *    4.1.弹出A的栈顶压入到B，如此反复直到弹出的符号为(,(和)不要压入B,跳转到1 
  
*/


/*  函数名：changeToSufficalExpression
*   参数  ：表达式的栈 要求 该栈是把 = 号为栈底  第一个数为栈顶
*	作用  ：把原表达式转换成后缀表达式
*   返回类型： 布尔型  转换成功就为 true 有问题就 false 
*/


bool  changeToSufficalExpression(stackList<float> &expression)

{
	stackList<char> expressionA ;//栈A存放运算符
	stackList<float> expressionB ;
	
	while(expression.getLength() > 0)
		
	{
		//符号 = 保存进栈A
		if((expression.getType() == 1)&&(expression.getTop() == '='))
			
		{
			
			char midTranslate ;
			char midTranslate1 ;
		
			midTranslate1 = expression.getTop() ;
			expression.pop() ;
			//把栈A中的运算符全部压进栈B中
			while(expressionA.getLength() > 0)
				
			{
				midTranslate = expressionA.getTop() ;
				expressionB.push(midTranslate) ;
				expressionB.setType(1);
				expressionA.pop() ;
			}
			expressionB.push(midTranslate1) ;
			expressionB.setType(1);
			continue;
		}
		
		//符号 + 保存进栈A
		else if((expression.getType() == 1)&&(expression.getTop() == '+'))
			
		{
			char midTranslate ;
			midTranslate = expression.getTop() ;
			while((expressionA.getTop() == '*')||(expressionA.getTop() == '/')||(expressionA.getTop() == '-'))
			{
				expressionB.push(expressionA.getTop()) ;
				expressionB.setType(1);
				expressionA.pop() ;
			}
			expressionA.push(midTranslate) ;
			expressionA.setType(1);
			expression.pop() ;
			continue;
			
		}
		
		//符号 - 保存进栈A
		else if((expression.getType() == 1)&&(expression.getTop() == '-'))
			
		{
			char midTranslate ;
			midTranslate = expression.getTop() ;
			while((expressionA.getTop() == '*')||(expressionA.getTop() == '/')||(expressionA.getTop() == '+'))
			{
				expressionB.push(expressionA.getTop()) ;
				expressionB.setType(1);
				expressionA.pop() ;
			}
			expressionA.push(midTranslate) ;
			expressionA.setType(1);
			expression.pop() ;
			continue;
		}
		
		//符号 * 保存进栈A
		else if((expression.getType() == 1)&&(expression.getTop() == '*'))
			
		{
			char midTranslate ;
			midTranslate = expression.getTop() ;
			while((expressionA.getTop() == '*')||(expressionA.getTop() == '/'))
			{
				expressionB.push(expressionA.getTop()) ;
				expressionB.setType(1);
				expressionA.pop() ;
			}
			expressionA.push(midTranslate) ;
			expressionA.setType(1);
			expression.pop() ;
			continue;
		}
		
		//符号 /  保存进栈A
		else if((expression.getType() == 1)&&(expression.getTop() == '/'))
			
		{
			char midTranslate ;
			midTranslate = expression.getTop() ;
			while((expressionA.getTop() == '*')||(expressionA.getTop() == '/'))
			{
				expressionB.push(expressionA.getTop()) ;
				expressionB.setType(1);
				expressionA.pop() ;
			}
			expressionA.push(midTranslate) ;
			expressionA.setType(1);
			expression.pop() ;
			continue;
		}
		
		//符号 (  保存进栈A
		else if((expression.getType() == 1)&&(expression.getTop() == '('))
			
		{
			char midTranslate ;
			float midTranslateB ;
			
			midTranslate = expression.getTop() ;
			expressionA.push(midTranslate) ;
			expressionA.setType(1) ;
			expression.pop() ;
			
			// 判断是否为负数 然后进行处理
			if((expression.getType() == 1)&&(expression.getTop() == '-'))
			{
				//从符号 - 出栈
				expression.pop();
				if(expression.getType() == 0)
				{
					midTranslateB = expression.getTop() ;
					expression.pop() ;
					midTranslateB = midTranslateB *(-1) ;
					expression.push(midTranslateB , 0);
				}
			}
			// 判断是否为正数 然后进行处理
			if((expression.getType() == 1)&&(expression.getTop() == '+'))
			{
				//从符号 + 出栈
				expression.pop();
				if(expression.getType() == 0)
				{
					midTranslateB = expression.getTop() ;
					expression.pop() ;
					midTranslateB = midTranslateB *1 ;
					expression.push(midTranslateB , 0);
				}
			}
			
			
			continue;
		}
		
		//符号 )  
		else if((expression.getType() == 1)&&(expression.getTop() == ')'))
			
		{
			char midTranslate ;
			midTranslate = expression.getTop() ;
			while(expressionA.getTop() != '(')
			{
				expressionB.push(expressionA.getTop()) ;
				expressionB.setType(1);
				expressionA.pop() ;
				//如果找不到 ' ( ' 则表达式有问题
				if(expressionA.getLength() == 0)
				{
					return false ;
				}
			}
			expressionA.pop() ;
			expression.pop() ;
			continue;
		}
		
		//数字 保存进栈B
		else
			
		{
			float midTranslate ;
			midTranslate = expression.getTop() ;
			expressionB.push(midTranslate) ;
			expressionB.setType(0);
			expression.pop() ;
		}
		
	}
	
	
	/*
	*	把栈B中的表达式重新弄入到原栈中
	*/
	while(expressionB.getLength() > 0)
		
	{
		
		float midTranslate ;
		int type ;
		
		midTranslate = expressionB.getTop() ;
		type = expressionB.getType() ;
		//检查括号是否匹配问题
		if((type == 1)&&(midTranslate == '('))
		{
			return false ;
		}
		expression.push(midTranslate,type) ;
		expressionB.pop();
	}
	
	
	
	return true ;
	
}


#endif