栈的应用—前、中、后缀表达式

x33g5p2x  于2021-09-19 转载在 其他  
字(2.3k)|赞(0)|评价(0)|浏览(527)
  • 中缀表达式:运算符在两个操作数中间
  • 前缀表达式:运算符在两个操作数前面(两个操作数的左右顺序不能颠倒)
  • 后缀表达式:运算符在两个操作数后面(两个操作数的左右顺序不能颠倒)

中缀表达式转后缀表达式的手算方法:

客观来说两种计算结果都正确,但是计算机算法计算的结果为前者,所以依据“左优先”原则得到的结果可以和计算机算法计算的结果相同,推荐使用左边计算方法即依据左优先原则。
左优先原则计算得到的后缀表达式中计算符从左到右的顺序和依据左优先原则的中缀表达式中的计算符的计算顺序相同。

后缀表达式的计算:

手算:

注意两个操作数的左右顺序。

机算:

因为后序表达式的每次计算都让运算符前面最近的两个操作数执行对应的计算,这与栈的后进先出原则相符,所以使用栈这个数据机构计算后缀表达式。

中缀表达式转前缀表达式的手算方法:
右边计算结果为根据右优先原则计算的结果,使用右优先原则的原因和及效果与左优先原则相同。只是根据右优先原则计算得到的前缀表达式中运算符从右到左的顺序和中缀表达式中运算符的计算顺序相同。

前缀表达式的计算:

注意:前缀表达式的计算顺序是从右到左,后缀表达式的计算顺序是从左到右。
手算原理与前缀表达式一样,都与计算相同。

中缀表达式转后缀表达式的代码实现:

后缀表达式又称为逆波兰表达式,后缀表达式在计算机领域有非常广泛的应用,中缀表达式转换成后缀表达式这个算法非常重要。

算法思路:

初始化一个栈,用来保存暂时还不能确定运算顺序的运算符。
从左到右处理中缀表达式中的各个元素,直到末尾,可能遇到三种情况:

1. 遇到操作数(数字之类);直接加入后缀表达式。
2. 遇到界限符(括号);遇到 ’ ( ’ 直接入栈;遇到 ’ ) ’ 则依次弹出栈内运算符并加入后缀表达式,直到弹出 ’ ( ’ 为止。注意:’ ( ’ 不加入后缀表达式。
3. 遇到运算符(加减乘除);依次弹出栈中优先级高于或等于当前运算符的所有运算符,并加入后缀表达式,若碰到 ’ ( ’ 或栈为空则停止。之后再把当前运算符入栈。
按上述方法处理完所有元素后,将栈中剩余运算符依次弹出,并加入后缀表达式中。

#include<iostream>
#include<unordered_map>
using namespace std;
//中缀表达式转成后缀表达式 

unordered_map<char,int>mp; //定义hash表记录运算符等级 

struct Stack{
	char data;
	Stack *next;
};

//初始化栈
void InitStack(Stack * &S){
	
	S=(Stack *)malloc(sizeof(Stack));
	S->next=NULL;
	
} 

//判断栈是否为空
bool IsEmpty(Stack * &S){
	
	return S->next==NULL;
	
} 

//入栈
void StackPush(Stack * &S,char value){
	
	Stack *p=(Stack *)malloc(sizeof(Stack));
	p->data=value;
	p->next=S->next;
	S->next=p;
	
} 

//出栈
void StackPop(Stack * &S){
	
	if(IsEmpty(S))
		return;
	
	Stack *p=S->next;
	S->next=p->next;
	free(p); 
	
} 

//取栈顶元素
char StackGetTop(Stack * &S){
	
	if(IsEmpty(S))
		return '!';
		
	return S->next->data;	
} 

//前缀表达式转换成后缀表达式
void Transform(Stack * &S,string &Qstr,string &Hstr){
	
	for(int i=0;i<Qstr.length();i++){
		
		if(Qstr[i]>='a'&&Qstr[i]<='z'||Qstr[i]>='A'&&Qstr[i]<='Z'){
			Hstr+=Qstr[i];
		}else if(Qstr[i]=='('){
			StackPush(S,'C');
		}else if(Qstr[i]==')'){		
			while(StackGetTop(S)!='('){
				Hstr+=StackGetTop(S);
				StackPop(S);
			}
			StackPop(S);
		}else{
			char c=Qstr[i];
			while(!IsEmpty(S)){
				
				char t=StackGetTop(S);
				if(t=='('){
					break;
				}
					
				if(mp[t]>=mp[c]){
					Hstr+=t;
					StackPop(S);
				}else{
					break;
				}
			}
			StackPush(S,c);
		}
		
	}
	while(!IsEmpty(S)){
		Hstr+=StackGetTop(S);
		StackPop(S);
	}
} 
 

int main(){
	
	Stack *S; //定义一个栈
	string Zstr,Hstr=""; //定义前缀表达式 后缀表达式 
	mp['+']=1; mp['-']=1; mp['*']=2; mp['/']=2; //记录运算符等级 
	
	getline(cin,Zstr); //输入前缀表达式 
	
	InitStack(S); //初始化栈 
	
	Transform(S,Zstr,Hstr); //前缀表达式转换成后缀表达式 
	
	cout<<Hstr; //输出后缀表达式 
	
	return 0;
} 

/** A+B-C*D/E+F AB+CD*E/-F+ */

相关文章