中缀表达式转换为后缀

1.算法描述

 

例如a+b*c这是常见的中缀表达式，但是为了方便计算，在计算机中常要转换为后缀表达式abc*+的形式，那

如何转换呢？

 

用到的关键数据结构:栈

转换的关键原则：

 

1.优先级判断：关键是比较运算符的优先级,谁的优先级高,谁就出现在前面上面的表达式中,有括号的时候括号优先级最高,*

/次之,+-最后. 在上面的表达式中+的优先级不如*的高,因此,在后缀表达式中*出现在+前面, 

2.操作数处理：遇到操作数的时候总是直接输出,不做任何比较 

3.括号处理：遇到左括号总是直接入栈,遇到右括号的时候总是弹栈,一直弹到遇到一个左括号 

4.优先级处理：遇到操作符的时候就先将这个操作符和它前面的操作符比较优先级

a.高于前面(栈顶)的优先级,先将它压栈;

b.低于或等于前面的操作符的优先级,就把前面的优先级比它高的或相等的顺序弹出来, 一直弹到遇到优先级比它还低的或者到了栈顶，然后在压栈.

 

2.优先级

enum{FLAG = -1,  // FLAG为栈顶标志,优先级最低，这样做的目的在于任何操作符都能够压栈（4.优先级处理中有说明）

L_BRCAKET = 0,  // 次与上面，目的在于所有操作符都能在（之后压栈（3.括号处理）

PLUS = 1, //然后其他就按常规规定

MINUS = 1, 

MULTIPLY = 2,

DIVISON = 2,

PERSENT = 2,

POWER = 2};

分别为左括号,加减乘除的优先级定义,这儿有一个 FLAG = -1.是做什么咧? 

假如分析上面的4点就会发现,有一些特例,比如第一个操作符入栈之前要跟前面的操作符比较优先级,

但是前面还没有操作符,就只好当做一个特例特别处理,先判断是否栈为空,然后操作, 假如我们先将 一个标志符号压入栈,

并让它的优先级低于其他所有的操作符的优先级,这样它就永远不会被弹出, 而且消除了特例的判断,这是技巧 

另外注意,把左括号的优先级定义的很低,这也是有道理的.因为我们总是当遇到右括号的时候才把左括号弹出来.. 

 

 

3.判断伪代码：

for(遍历所有字符){

  if(数字) 输出；

else{

if(左括号)  入栈;

else if(右括号) 弹栈,一直弹到遇到一个左括号；

else{

判断操作符优先级；

if(栈顶优先级小于当前优先级){

压栈；

}else{

将小于当前优先级的所有操作符出栈，然后入栈；

}

}

}

}

 

4.代码

 

#include <iostream>
#include "stack.h"
#include <cstring>
using namespace std;

//定义操作符优先级
enum{ FLAG = -1, // FLAG为栈顶标志,优先级最低,此时根据规则，则所有操作符都可以入栈
			L_BRACKET = 0, //左括号优先级最低
			PLUS = 1,
			MINUS = 1, 
			MULTIPLY = 2, 
			DIVISON = 2,
			PERSENT = 2,
			POWER = 2;
};

//获取操作符优先级
int getPri(char ch){
	switch(ch){
		case  '+':
			return PLUS;
		case '-':
			return MINUS;
		case '*':
			return MULTIPLY;
		case '/':
			return DIVISON;
		case '%':
			return PERSENT;
		case '^':
			return POWER;
		case '(':
			return L_BRACKET;
		case '#':
			return FLAG;
	}
}

//判断是否是操作符
bool isOper(char ch){
	if((ch == '+') || (ch == '-') || (ch == '*') || (ch == '/') || (ch == '%') || (ch == '^'))
		return true;
	return false;
}

//判断是否是括号
bool isBracket(char ch){
	if(ch == '(' || ch == ')')
		return true;
	else
		return false;
}

int main(){
	//string infix = "10/(2+3)"; (1+2)/2+(3+5)*7; "2*3/5-(2*3)"
	string infix = "(1+2+3)/2/3+(3+5)*7";
	cout<<"中缀表达式:"<<infix<<endl;
	stack<char> opt; 									//栈
	opt.push('#'); 										//#作为栈底结束
	int len = infix.length(); 
	int flag = 0;											//记录结果
	char* result = new char[len];			//存储结果
	
	
	for (int i = 0; i < len; i++) 
	{ 
		char ch = infix.at(i);
		//1.判断是否是操作数，如果是则直接打印，否则继续判断
		if(!isOper(ch) && !isBracket(ch)){
			result[flag++] = ch;
		}
		//2.如果是操作符，则判断是哪种类型，若是(则直接入栈，其他判断优先级决定出入栈
		else{													
			if(ch == '('){								//a.（则入栈
				opt.push(ch);
			}else if(ch == ')'){					//b.如果是）则，全部出栈，直到遇到(
				while(opt.top() != '('){
					result[flag++] = opt.pop();
				}
				opt.pop();									//最后一个'('出栈
		
			}else{												//c.判断操作符+,-,*,/...
				char t = opt.top();				  //首先，看当前栈顶是什么操作符
				int pre = getPri(t);
				int cur = getPri(ch);
				//A.操作符比较规则1：高于栈顶的优先级,先将它压栈
				//(这里用了一个技巧，当栈为空此时栈底是'#'优先级最低-1，其次是'('为0，这样所有操作符此种情况都可入栈)
				if(cur > pre){
					opt.push(ch);
				}
				//B.操作符比较规则2：小于等于栈顶的优先级,把前面的优先级比它高的或相等的顺序弹出来, 一直弹到遇到优先级比它还低的或者到了栈顶,然后在压栈
				else{
					result[flag++] = opt.pop();
					pre = getPri(opt.top());
					while(pre >= cur){
						result[flag++] = opt.pop();
						pre = getPri(opt.top());
					}
					opt.push(ch);							//最后不要忘记将当前（优先级相同）的ch压栈
				}
			}
		}
		
	} 
	
	char ch = opt.top(); // 表达式扫描完后把栈中剩余的操作符全部输出 
	while (ch != '#') 
	{
		result[flag++] = ch; 
		opt.pop(); 
		ch = opt.top(); 
	} 
	//输出结果
	cout<<"后缀表达式:";
	for(int i=0; i<flag; i++){
		cout<<result[i];
	}
	cout<<endl;
	delete[] result;
	return 0;
}

 5.

注1：栈stack.h和后缀表达式的计算见http://hao3100590.iteye.com/blog/1569122

谢谢！