qianzhui.txt

前缀表达式 自己写的

/*9.从原四则表达式求得前缀表达式
利用栈将中缀表达式转成前缀表达式的思路：
1）求输入串的逆序。
2）检查输入的下一元素。
3）假如是操作数，把它添加到输出串中。
4）假如是闭括号，将它压栈。
5）假如是运算符，则
i)假如栈空，此运算符入栈。
ii)假如栈顶是闭括号，此运算符入栈。
iii)假如它的优先级高于或等于栈顶运算符，此运算符入栈。
iv)否则，栈顶运算符出栈并添加到输出串中，重复步骤5。
6）假如是开括号，栈中运算符逐个出栈并输出，直到遇到闭括号。闭括号出栈并丢弃。
7）假如输入还未完毕，跳转到步骤2。
8）假如输入完毕，栈中剩余的所有操作符出栈并加到输出串中。
9）求输出串的逆序。
*/
#include <stdio.h>
#include <iostream>
#include <stack>
#include <malloc.h>
using namespace std;
char oper[8][8]={{'0','+','-','*','/','(',')','#'},
{'+','>','>','<','<','<','>','>'},
{'-','>','>','<','<','<','>','>'},
{'*','>','>','>','>','<','>','>'},
{'/','>','>','>','>','<','>','>'},
{'(','<','<','<','<','<','=',' '},
{')','>','>','>','>',' ','>','>'},
{'#','<','<','<','<','<',' ','='},
};

int precede(char o1,char o2){
	for(int i=0;i<8;i++){
		for(int j=0;j<8;j++){
			if(oper[0][j]==o2&& oper[i][0]==o1) {
				if(oper[i][j]=='>') return 1;
			}//if
		}//for
	}//for
	return 0;
}

char panduan(char ch){
	if(ch>='a'&&ch<='z')return 's';
	if(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='#')return 'o';
	if(ch==')')return ')';
	if(ch=='(')return '(';
	return '0';
}
void main(){
	char exp[100];
	char ca,chara;
	int i=0;
	int n=0;
	stack<char> S;
	stack<char> output;
    //输入
	cout<<"请输入四项表达式(以'#'结束)："<<endl;
	cin>>exp[i];n=n+1;
	while(exp[i]!='#'){
		++i;
		cin>>exp[i];
		n++;
	}
	for(i=n-2;i>=0;i--){
        chara=panduan(exp[i]);
		//cout<<exp[i];
		//cout<<chara;
        switch(chara){
		case ')': S.push(exp[i]);break;//假如是闭括号，将它压栈
		case 'o':             //假如是运算符，则
			while(exp[i]!='#'){
				if(S.empty()) {S.push(exp[i]);break;}//假如栈空，此运算符入栈。	               
			    ca=S.top();//if(ca=S.top()&&ca==')' ){S.push(exp[i]);break;}//假如栈顶是闭括号，此运算符入栈。
				if(precede(exp[i],ca))	{cout<<precede(exp[i],ca)<<endl;S.push(exp[i]);break;}//假如它的优先级高于或等于栈顶运算符，此运算符入栈。
				else {                      //栈顶运算符出栈并添加到输出串中
		      		ca=S.top();
		    		output.push(ca);
		    		S.pop();
				}
			}
			break;
		case '(':              //假如是开括号，栈中运算符逐个出栈并输出，直到遇到闭括号。闭括号出栈并丢弃。
			ca=S.top();
			while(ca!=')'){
				S.pop();
				output.push(ca);	
			}
			S.pop();
			break;
		case 's':output.push(exp[i]);break;//假如是操作数，把它添加到输出串中。
		default:break;
		}//for
	}//switch
	//输入完毕，栈中剩余的所有操作符出栈并加到输出串中。
	while(!S.empty()){
		ca=S.top();
		output.push(ca);
		S.pop();
	}
	//打印
	cout<<"前缀表达式："<<endl;

	while(!output.empty()){
	    ca=output.top();
		output.pop();
		cout<<ca;
	
	}
    
}