二叉树实现中缀表达式转换为后缀表达式 小小问题 望看下
#include <stdio.h>#include <string.h>
#include <malloc.h>
#include <stdlib.h>
#include <stack>
#include <string.h>
#define STACK_INIT_SIZE 100
#define DATA_SIZE 10
#define STACKINCREMENT 10
#define OK 1
#define TRUE 1
#define FALSE 0
#define ERROR 0
#define OVERFLOW -2
using namespace std;
typedef float SElemtype;
typedef int Status;
typedef char * TElemType;
typedef struct BiTNode {
TElemType data;
int len; //data字符串中字符的个数
struct BiTNode * lchild, * rchild;
}BiTNode, *BiTree;
Status IsDigital(char ch)
{
if(ch>='0'&&ch<='9')
{
return 1; //是数字字母
}
return 0; //不是数字字母
}
int CrtNode(stack <BiTree> &PTR, char *c)
{
BiTNode * T;
int i=0;
T = (BiTNode *)malloc(sizeof(BiTNode));
T->data = (char *)malloc(DATA_SIZE*sizeof(char));
while(IsDigital(c[i]))
{
T->data [i] = c[i];
i++;
}
T->len = i;
T->lchild = T->rchild = NULL;
PTR.push (T);
return i;
}
void CrtSubTree(stack <BiTree> &PTR, char c)
{
BiTNode * T;
T = (BiTNode *)malloc(sizeof(BiTNode));
T->data = (char *)malloc(DATA_SIZE*sizeof(char));
T->data [0] = c;
T->len = 1;
T->rchild = PTR.top(); //先右子树，否则运算次序反了
PTR.pop ();
T->lchild = PTR.top();
PTR.pop ();
PTR.push (T);
}
char symbol[5][5]={{'>', '>', '<', '<', '>'}, //符号优先级
{'>', '>', '<', '<', '>'},
{'>', '>', '>', '>', '>'},
{'>', '>', '>', '>', '>'},
{'<', '<', '<', '<', '='}};
int sym2num(char s) //返回符号对应优先级矩阵位置
{
switch(s)
{
case '+': return 0; break;
case '-': return 1; break;
case '*': return 2; break;
case '/': return 3; break;
case '#': return 4; break;
}
}
char Precede(char a, char b) //返回符号优先级
{
return(symbol[sym2num(a)][sym2num(b)]);
}
void CrtExptree(BiTree &T, char exp[])
{//根据字符串exp的内容构建表达式树T
stack <BiTree> PTR;//存放表达式树中的节点指针
stack <char> OPTR;//存放操作符
char op;
int i=0;
OPTR.push ('#');
op = OPTR.top();
while( !((exp[i]=='#') && (OPTR.top()=='#')) ) //与
{
if (IsDigital(exp[i]))
{//建立叶子节点并入栈 PTR
i+=CrtNode(PTR, &exp[i]);
}
else if (exp[i] == ' ')
i++;
else{
switch (exp[i])
{
case '(': {
OPTR.push (exp[i]);
i++;
break;}
case ')': {
op = OPTR.top (); OPTR.pop ();
while(op!='('){
CrtSubTree(PTR, op);
op = OPTR.top (); OPTR.pop ();
}//end while
i++;
break;}
default: //exp[i]是 + - * /
while(! OPTR.empty ())
{
op = OPTR.top ();
if (Precede(op, exp[i])=='>')
{
CrtSubTree(PTR, op);
OPTR.pop ();
}
if(exp[i]!='#')
{
OPTR.push (exp[i]);
i++;
}
break;}
}//end switch
}//end else
}//end while
T = PTR.top();
PTR.pop ();
}
void PostOrderTraverse(BiTree &T, char * exp ,int &count)
{
//后序遍历表达式树T，获取树中每个结点的数据值生成 逆波兰表达式 exp
//T是表达式树的根节点；字符串exp保存逆波兰表达式；count保存exp中字符的个数
//后序遍历中，处理根结点时，依据T->len的值，把T->data中的字符依次添加到当前exp字符串的尾端
//添加完T->data后，再添加一个空格字符，同时更新count计数器的值。
//填空
int i;
if(T){
PostOrderTraverse(T->lchild);
//后序访问左子树
PostOrderTraverse(T->rchild);
//后序访问右子树
for(i=0;i<=T->len;i++)
{exp(i)=T->data;
count++;
}
}
return OK;
}//PostOrderTraverse
}
//填空
evaluate (char *exp,float ans) //逆波兰表达式计算
{int i,top=0;
float d,m,n;
while(exp[i++]!='#')
{d=exp(i++)-'0';
if(exp[i++]>='0' && exp[i++]<='9')
{top++;
push(Stack,exp[i++]);
}
else
{switch(exp[i++])
{ case '+':push(Stack,pop(Stack,m)+pop(Stack,n));break;
case '-':push(Stack,pop(Stack,m)-pop(Stack,n));break;
case '*':push(Stack,pop(Stack,m)*pop(Stack,n));break;
case '/':
if(n!=0)
push(Stack,pop(Stack,m)/pop(Stack,n));
else printf("Error\n");
break;
}
top--;
}
}
ans=Stack[top];
printf("%f\n",Stack[top]);
}
main()
{
BiTree T;
Status St;
char ch[100],c; //输入的四则运算表达式
char exp[100]; //逆波兰表达式
int count=0;
int i=0;
float result;
printf("请输入表达式。回车表示结束\n");
while(i<100)
{
scanf("%c",&c);
ch[i++]=c;
if(c=='\n'){
ch[--i]='#';
break;
}//end if
}
CrtExptree(T, ch);//根据字符串ch的内容构建表达式树T
//后序遍历表达式树T得到表达式的 逆波兰表达式 exp；count中保存exp中
PostOrderTraverse(T, exp, count);
printf("逆波兰表达式为\n");
for(i=0; i<count; i++)
printf("%c",exp[i]);
printf("\n");
exp[count] = '#'; //添加结束符
St = evaluate (exp, result); //计算 逆波兰表达式 exp 的值
//输出计算的结果
if (St)
printf("result is %5.2f \n", result);
else
printf("\n表达式错误\n");
return 0;
}
注：编译是出现Cannot open include file: 'exception': No such file or directory
的情况.程序不能运行....
[ 本帖最后由 wwlyf52o1314 于 2010-4-19 22:30 编辑 ]
