C++实现中缀转后缀的示例详解

单位数加减乘除

例如：2+3*(4-9)

定义一个栈内优先级

运算符号优先级+、-3*、/5(1)6#0

定义一个栈外优先级

运算符号优先级+、-4*、/2(6）1#0

整个过程如下：

首先将#入栈，这是为了让运算符与栈内的符号进行比较是否入栈，否则无法判断

1. 2为数字，直接输出
2. +和#进行运算符比较，因为+的优先级大于#，入栈
3. 3为数字，直接输出
4. (和+进行比较，（的优先级比+大，将+取出输出，将（入栈
5. 4为数字，直接输出
6. -的优先级比’（‘大，直接入栈。注意：此时的’（'为栈内优先级
7. 9为数字。直接输出
8. )优先级比-大，取出-，同时()配对了，也要将（取出
9. 最后遍历栈内运算符即可

需要注意的点是：

就像这样栈内的头顶两个元素这样(+，下一个符号刚好是)，需要考虑到，取完+号后，需要把（也去取出来

实现代码

#include<iostream>
#include<stack>
#include<string>
using namespace std;
//栈内优先级
int CompareIn(char c){
	if(c=='('){
		return 1;
	}
	if(c=='+'||c=='-'){
		return 3;
	}
	if(c=='*'||c=='/'){
		return 5;
	} 
	if(c==')'){
		return 6;
	}
	if(c=='#'){
		return 0;
	}
}
//栈外优先级 
int CompareOut(char c){
	if(c=='('){
		return 6;
	}
	if(c=='+'||c=='-'){
		return 2;
	}
	if(c=='*'||c=='/'){
		return 4;
	} 
	if(c==')'){
		return 1;
	}
	if(c=='#'){
		return 0;
	}
}
int main(){
	string str;
	cin>>str;
	stack<char> q;
	q.push('#');
	for(int i=0;i<str.length();i++){		
		if('1'<=str[i]&&str[i]<='9'){
			cout<<str[i];
		}else{
			if(CompareIn(q.top())<CompareOut(str[i])){
				q.push(str[i]);
			}else if(CompareIn(q.top())==CompareOut(str[i])){
				q.pop();
			}else if(CompareIn(q.top())>CompareOut(str[i])){
				char ch=q.top();
				q.pop();
				cout<<ch;
				if(str[i]!=')'){
					q.push(str[i]);
				}	
			   if(CompareIn(q.top())==CompareOut(str[i])){
				q.pop();
		    	}
			}
		}
	}
	while(CompareIn(q.top())!=0){
		cout<<q.top();
		q.pop();
	}
	
}
}

到此这篇关于C++实现中缀转后缀的示例详解的文章就介绍到这了,更多相关C++中缀转后缀内容请搜索自由互联以前的文章或继续浏览下面的相关文章希望大家以后多多支持自由互联！