main.cpp

中缀表达式改后缀表达式

#include<string>
#include<iostream>
#include<vector>
#include"t_node.h"
using namespace std;

 //判断c是否是操作符
bool judge(char c);

//在c中下标在first和last之间的最小元素的下标
int  findmin(vector<int> c,int first,int last);  

// 把输入的表达式字符窜进行处理，把每个操作数和操作符依次保存在b中，在c中保存相应分优先级
void translate(string a,vector<string> &b,vector<int> &c); 

//转变成表达式数
void trantotree(vector<string> b,vector<int> c,t_node *root);

//进行后序遍历
void search(t_node *root);

//清除该树占用的内存
void deletetree(t_node *root);

void main()
{
	string s;
    vector<string> v1;
	vector<int> v2;
	t_node *root=new t_node(); 
	cout<<"请输入中缀表达式："<<endl;
    cin>>s;
	translate(s,v1,v2);
    trantotree(v1,v2,root);
	cout<<"后序遍历结果为："<<endl;
	search(root);
	cout<<endl;
	deletetree(root);
}



void deletetree(t_node *root)
{
	if(root!=NULL)
	{
		deletetree(root->left);
        deletetree(root->right);
		delete root;
	}

}


void search(t_node *root)
{
	if(root!=NULL)
	{
		search(root->left);
		search(root->right);
		cout<<root->value<<" ";
	}

}

int rank(char ch)
{
	if(ch=='+'||ch=='-')
		return 1;
	else if(ch=='*'||ch=='/'||ch=='%')
		return 100;
	else
		return 1000;


}

bool judge(char c)
{
	if(c=='+'||c=='-'||c=='*'||c=='/'||c=='%')
		return true;
	else 
		return false;
}


int findmin(const vector<int> c,int first,int last)
{
	int temp=c[last],k=last;
	for(int i=last-1;i>=first;i--)
	{
		if(c[i]<temp)
		{
			k=i;
			temp=c[k];
		}
	}
	return k;
}


void trantotree(vector<string> b,vector<int> c,t_node *root)
{
	if(b.size()==1)
		root->value=b[0];

	
   else
   {
	   vector<string> b1,b2;
	   vector<int> c1,c2;
	   int i,j;
	   i=findmin(c,0,c.size()-1);
       root->value=b[i];
	   for(j=0;j<i;j++)
	   {
		   b2.push_back(b[j]);
		   c2.push_back(c[j]);
	   }
	   root->left=new t_node();
       trantotree(b2,c2,root->left);
	   for(j=i+1;j<c.size();j++)
	   {
		   b1.push_back(b[j]);
	       c1.push_back(c[j]);
	   }
       root->right=new t_node();	
       trantotree(b1,c1,root->right);
   }


}


void translate(string a,vector<string> &b,vector<int> &c)
{
	int len=a.length();
	int i=0,j=0,k=0;
	string s="";
	while(i<len)
	{
		if(a[i]=='(')
		{
			k++;
			i++;
			continue;
		}
				
		if(a[i]==')')
		{
			k--;
			i++;
			continue;
		}
        if(!judge(a[i]))
		{
			s=s+a[i];
			i++;
		}
        else
		{
			string d="";
			b.push_back(s);
            c.push_back(1000);
			b.push_back(a[i]+d);
			c.push_back(rank(a[i])+k*100);
			s="";
			i++;
			
				    
		}
	}
	b.push_back(s);
    c.push_back(1000);
           


}