biadashi .txt

表达式的一个算法,没有错误,可以运行,是我们老师告诉我的.

#include <iostream.h>
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>


//定义全局变量
int n=0,i=0,m=0;      //n记录字符的个数，i记录当前输入的是第几个字符，m记录变量的个数
char a[100],b[100];  //记录相应的变量符和存入变量值


//定义一个结构体
typedef struct tree 
{
       char data;         //存放字符
       struct tree *lchild;
       struct tree *rchild;
}tree,*bitree;
 

int get(int op, int operand1, int operand2);
void assign(char &V, char c);


void createbitree( bitree &T)
{//以前缀的方式输入字符，创建一个树结构
	char ch;
	i++;

    cin >> ch;

	if(ch == '!' || i > n)T = NULL;
	else{
		if(ch >= 'a' && ch <= 'z')
		{
			if(m < 1)      //当是第一个字符时，直接放入数组的第一个元素
				{
			m ++;
			a[m] = ch;
				}
			else         //否则进行查找，若前面没出现过则插入数组
			{
			for(int j = 1; j <= m; j++)
				if(ch == a[j])break;
				if(j > m)  //没有找到重复的字符
				{
			m ++;
			a[m] = ch;
				}
			}
		}
		T = (bitree)malloc(sizeof(tree));   //动态开辟一个结点的空间
	    T -> data = ch;                       //将输入的字符赋值给结点
		createbitree(T -> lchild);
		createbitree(T -> rchild);
	}
}


void assign(char &V, char c)
{
	V = c;            //给变量赋值
}


 void fuzhi(struct tree *T, char x, char y)
{

	 if (T != NULL )
	 {
		 if('a' <= T->data && T->data <= 'z')   //判断结点中的数据是不是变量
			 if(T -> data == x)       //是变量则将输入的相应值赋给变量
	         assign(T -> data, y);
          fuzhi(T -> lchild, x, y);
          fuzhi(T -> rchild, x, y);
	 }
}


 void preorder(struct tree *T)     //按前缀表示式输出表达式
{
	 if (T != NULL )
	 {
      cout << T->data;
      preorder(T -> lchild);
      preorder(T -> rchild);
	 }
}


void inorderexp(struct tree* T)    //按中缀表示式输出表达式，并加括号
{
	if(T != NULL)
	{
		if(T -> lchild){
			cout << "(";
            inorderexp(T -> lchild);
			cout << ")";}
		cout << T -> data;
		if(T -> rchild){
			cout << "(";
            inorderexp(T -> rchild);
			cout << ")";}
	}
}


void lastorder(struct tree *T)   //按后缀表示式输出表达式
{
    if (T != NULL )
	{
		lastorder(T -> lchild);
        lastorder(T -> rchild);
        cout << T -> data;
	}
}


int cal (struct tree *T)
{//利用后根遍历对表达式求值
     int operand1 = 0;
     int operand2 = 0;
     if (T -> lchild == NULL && T -> rchild == NULL)
     return (int)(T -> data) - 48;
     else
	 {
        operand1=cal(T -> lchild);
        operand2=cal(T -> rchild);
        return get(T -> data, operand1, operand2);
	 }
}


int get(int op, int operand1, int operand2)
{
	int i;
    int t;
switch ((char)op)    //对符号进行判断，执行相应的操作
{
case '^':
	t = operand1;
for(i = 1; i < operand2; i ++)
operand1 = operand1*t;
return operand1;break;
case '*': return operand1 * operand2;break; 
case '/': return operand1 / operand2;break;
case '+': return operand1 + operand2;break;
case '-': return operand1 - operand2;break;
}
}


int main()
{

	bitree T;
    int result;

	cout << "请输入字符的个数：";
    cin >> n;

    cout << "请以前缀表示法输入表达式：";
    createbitree(T);     //构造数结构

	cout << "此二叉树的前序遍历为：";
    preorder(T);
	cout << endl;

	cout << "此二叉树的中序遍历为：";
    inorderexp(T);
	cout << endl;

	cout << "此二叉树的后序遍历为：";
    lastorder(T);
	cout << endl;

	for(int i = 1; i <= m; i ++)
	{
		cout << "请输入" << a[i] << "的值：";
	    cin >> b[i];
    fuzhi(T,a[i],b[i]);
	}

	result = cal(T);      //计算表达式的值
	cout << "表达式的值为：" << result;
	cout << endl;

	return 1;
}