func.cpp
#include<iostream>
#include "head.h"
#include "postfix.h"
#include "Dstack.h"
using namespace std;
void main()
{
string infixEXP;
// cout<<"note:enter # for infix expression to stop"<<endl;
cout<<"中缀表达式为：";
getline(cin,infixEXP);
string c=postfix(infixEXP);
cout<<"后缀表达式为："<<postfix(infixEXP)<<endl;
Tnode *root;
int deep;
root=creatTree(c);
deep=depth(root);
print(root,deep);
cout<<endl;
}
/*
#include<iostream>
#include "Dstack.h"
using namespace std;
int main()
{
stack<int> s;
s.push(1);
return 0;
}
*/
postfix.h头文件
#include<iostream>
#include<string>
#include<cctype>
using namespace std;
#include "Dstack.h"
string postfix(string exp)
{
char token;//exp中的字符
string s;
stack<char>opstack;
string postfixExp;
for(int i=0;i<exp.length();i++)
{
token=(char)exp[i];
switch(token)
{
case' ':
break;
case'(':
opstack.push(token);
break;
case')':
while(opstack.top()!='(')//不到（的时候一直弹出
{
s=opstack.top();
postfixExp.append(s);
opstack.pop();
}
opstack.pop();
break;
case'+':
case'-':
case'*':
case'/':
case'%':
if(opstack.empty()|| opstack.top()=='('||(token=='*'||token=='/'||token=='%')&&(opstack.top()=='+'||opstack.top()=='-'))
{
opstack.push(token);
}
else
{
s=opstack.top();
postfixExp.append(s);
opstack.pop();
if(opstack.top()=='+'||opstack.top()=='-')
{
s=opstack.top();
postfixExp.append(s);
opstack.pop();
}
opstack.push(token);
}
break;
default:
s=token;
postfixExp.append(s);
break;
}
}
while(!opstack.empty())
{
s=opstack.top();
postfixExp.append(s);
opstack.pop();
}
return postfixExp;
}
Dstack.h头文件
#include<iostream>
#include<string.h>
using namespace std;
#define MaxSize 200
#ifndef Dstack
#define Dstack
template<typename T>
class stack{
private:
int ttop;
T array[200];
public:
stack();
void push(const T &value);
void pop();
bool empty() const;
T& top(void);
int size();
};
template<typename T>
stack<T>::stack()
{
ttop=-1;
}
template<typename T>
void stack<T>::push(const T & value)
{
if(ttop<MaxSize-1)
{
++ttop;
array[ttop]=value;
}
}
template<typename T>
bool stack<T>::empty() const
{
return (ttop==-1);
}
template<typename T>
T& stack<T>::top(void)
{
return(array[ttop]);
}
template<typename T>
void stack<T>::pop()
{
if(!empty())
ttop--;
else
cout<<"the stack is empty";
}
template<typename T>
int stack<T>::size()
{
return ttop+1;
}
#endif
head.h头文件
#include<iostream>
#include<string>
#include "Dstack.h"
#include<iomanip>
using namespace std;
class Tnode
{
public:
char oper;
Tnode *left;
Tnode *right;
Tnode(){}
Tnode(char item)
{
oper=item;
left=NULL;
right=NULL;
}
};
/*void postOrder(Tnode *p)
{
if(p)
{
postOrder(p->left);
postOrder(p->right);
cout<<p->oper;
}
}*/
bool isOper(char item)//判断是否为运算符
{
char oper[]={'(',')','+','-','*','/','^','%'};
for(int i=0;i<sizeof(oper);i++)
{
if(item==oper[i])
{
return true;
}
}
return false;
}
Tnode* creatTree(string &str)
{
stack<Tnode*> nodestack;
Tnode *p;
char temp;
int i=0;
temp=str[i++];
while(temp!='\0')
{
if(!isOper(temp))
{
p=new Tnode(temp);
nodestack.push(p);
temp=str[i++];
}
else
{
p=new Tnode(temp);
if(!nodestack.empty())
{
p->right=nodestack.top();
nodestack.pop();
}
if(!nodestack.empty())
{
p->left=nodestack.top();
nodestack.pop();
}
nodestack.push(p);
temp=str[i++];
}
}
return p;
}
// template<typename T>
void print(Tnode *node_ptr,int depth)
{
if (node_ptr!= NULL)
{
print(node_ptr->right,depth+1);
cout << setw(4*depth) << " ";
cout << node_ptr->oper << endl;
print(node_ptr->left, depth+1);
}
}
// template<typename T>
int depth(Tnode *t)
{
int depthval,depthright,depthleft;
if(t==NULL)
return -1;
else
{
depthleft=depth(t->left);
depthright=depth(t->right);
depthval=1+(depthleft>depthright?depthleft:depthright);
}
return depthval;
}