qianzhui.cpp

前缀表达式 自己写的

//9.从原四则表达式求得前缀表达式

#include <stdio.h>
#include <iostream>
#include <stack>
#include <malloc.h>
using namespace std;
char oper[7][7]={
{'0','+','-','*','/','(',')'},
{'+','>','>','<','<','<','>'},
{'-','>','>','<','<','<','>'},
{'*','>','>','>','>','<','>'},
{'/','>','>','>','>','<','>'},
{'(','<','<','<','<','<','='},
{')','>','>','>','>',' ','>'},
};

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

char testch(char ch){
	if(ch>='a'&& ch<='z')return 's';
	if(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<100){
		i++;
		cin>>exp[i];
		n++;
	}
	cout<<"逆序表达式："<<endl;
	for(i=n-2;i>=0;i--){cout<<exp[i];}
	for(i=n-2;i>=0;i--){
        chara=testch(exp[i]);
        switch(chara){
		case ')': S.push(exp[i]);break;//假如是闭括号，将它压栈
		case 'o':             //假如是运算符，则
			while(1){
				if(S.empty()) {S.push(exp[i]);break;}//假如栈空，此运算符入栈。	               
				else{
					ca=S.top();
				    if(ca==')' ){S.push(exp[i]);break;}//假如栈顶是闭括号，此运算符入栈。
				    else if( precede(exp[i],ca)==1)	{S.push(exp[i]);break;}//假如它的优先级高于栈顶运算符，此运算符入栈。
				    else {                      //栈顶运算符出栈并添加到输出串中
		      		    ca=S.top();
		    		    output.push(ca);
		    	    	S.pop();
					}
				}
			}
			break;
		case '(':              //假如是开括号，栈中运算符逐个出栈并输出，直到遇到闭括号。闭括号出栈并丢弃。
			ca=S.top();
			while(ca!=')'){
				output.push(ca);
				S.pop();
				ca=S.top();
			}
			S.pop();
			break;
		case 's':output.push(exp[i]);break;//假如是操作数，把它添加到输出栈中。
		default:break;
		}//for	
	}//switch
	//表达式判断完后，S不为空，则将S中所有操作符加入到输出栈中
	while(!S.empty()){
		ca=S.top();
		output.push(ca);
	    S.pop();	
	}
	//打印
	cout<<endl;
	cout<<"前缀表达式："<<endl;
	while(!output.empty()){
	    ca=output.top();
		output.pop();
		cout<<ca;	
	}
	cout<<endl;   
}