NOJ数据结构021——逆波兰表达式

系统管理员 2022-10-14 11:00 189阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MzA2ODI2OQ_size_16_color_FFFFFF_t_70]

本题要求采用有向无环图的邻接表表示，但我实在不会，参考其他大佬的做法，大部分都是用二叉树表示的（二叉树本身就是特殊的有向无环图），我也就用了二叉树表示（然后再换成邻接表？）。

代码：

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define MAX 2000
    
    typedef enum {
         charctor, operat }flag;
    //括号和字母为前， 运算符为后
    
    typedef struct Node {
        
    	char elem;//字符
    	int prio; //优先级
    	flag tag; //标志
    }Node;
    
    typedef struct BiNode{
        
    	Node data;
    	struct BiNode* left, * right;
    }BiNode, *BiTree;
    
    typedef struct NewString {
        
    	Node data[MAX];
    	int length;    //字符串长度
    }NewString;
    
    NewString InitString();   //初始化字符串
    int FindMid(NewString* S);//找到优先级最低的运算符的位置
    void ClearBrackets(NewString* S);   //去除最外层多余括号
    BiTree CreateTree(NewString* S);   //创建二叉树
    void LRDPrint(BiTree T);   //后序遍历输出
    
    int main()
    {
        
    	NewString S;
    	S = InitString();
    	BiTree T;
    	T = CreateTree(&S);
    	LRDPrint(T);
    	return 0;
    }
    
    NewString InitString()
    {
           //初始化字符串
    	char str[MAX];
    	NewString S;
    	int len, baselevel = 0;//字符串长度，基础优先级
    	scanf("%s", str);
    	len = strlen(str);
    	S.length = len;
    	for (int i = 0; i < len; i++) {
        
    		S.data[i].elem = str[i];
    		if (str[i] == '+' || str[i] == '-') {
        
    			//‘+’、‘-’的优先级比基础优先级大1
    			S.data[i].tag = operat;
    			S.data[i].prio = baselevel + 1;
    		}
    		else if (str[i] == '*' || str[i] == '/') {
        
    			//‘+’、‘-’的优先级比基础优先级大2
    			S.data[i].tag = operat;
    			S.data[i].prio = baselevel + 2;
    		}
    		else if (str[i] == '(') {
        
    			//基础优先级增大2
    			S.data[i].tag = charctor;
    			baselevel += 2;
    		}
    		else if (str[i] == ')') {
        
    			//基础优先级减小2
    			S.data[i].tag = charctor;
    			baselevel -= 2;
    		}
    		else {
        
    			//字母无优先级
    			S.data[i].tag = charctor;
    		}
    	}
    	return S;
    }
    
    void ClearBrackets(NewString* S)
    {
           //去除最外层多余括号
    	int level = 0;
    	if (S->data[0].elem == '(' && S->data[S->length - 1].elem == ')') {
        
    		//只有最左端与最右端的括号匹配时，才可去
    		for (int i = 0; i < S->length - 2; i++) {
        
    			if (S->data[i].elem == '(') {
        
    				level++;
    			}
    			else if (S->data[i].elem == ')') {
        
    				level--;
    			}
    			if (level == 0) {
        
    				return;
    			}
    		}
    		for (int i = 0; i < S->length - 2; i++) {
        
    			S->data[i] = S->data[i + 1];
    		}
    		S->length = S->length - 2;
    	}
    }
    
    int FindMid(NewString* S)
    {
           //找到优先级最低的运算符的位置
    	int pos = 0, min = 32768;
    	for (int i = 0; i < S->length; i++) {
        
    		if (S->data[i].tag == operat && S->data[i].prio <= min) {
        
    			min = S->data[i].prio;
    			pos = i;
    		}
    	}
    	return pos;
    }
    
    BiTree CreateTree(NewString *S)
    {
           //创建二叉树
    	BiTree T;
    	T = (BiTree)malloc(sizeof(BiNode));
    	NewString* left, * right;
    	left = (NewString*)malloc(sizeof(NewString));
    	right = (NewString*)malloc(sizeof(NewString));
    	int midpos, len;
    	len = S->length;
    	if (len == 1) {
        
    		T->data = S->data[0];
    		T->left = NULL;
    		T->right = NULL;
    	}
    	else {
        
    		midpos = FindMid(S);
    		left->length = midpos;
    		for (int i = 0; i < left->length; i++) {
        
    			left->data[i] = S->data[i];
    		}
    		right->length = S->length - midpos - 1;
    		for (int i = 0; i < right->length; i++) {
        
    			right->data[i] = S->data[i + midpos + 1];
    		}
    		ClearBrackets(left);
    		ClearBrackets(right);
    		T->data = S->data[midpos];
    		T->left = CreateTree(left);
    		T->right = CreateTree(right);
    	}
    	return T;
    }
    
    void LRDPrint(BiTree T)
    {
           //后序遍历输出
    	if (T == NULL) {
        
    		return;
    	}
    	else {
        
    		LRDPrint(T->left);
    		LRDPrint(T->right);
    		printf("%c", T->data.elem);
    	}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MzA2ODI2OQ_size_16_color_FFFFFF_t_70]: /images/20221014/b55d96d0a2c04848ac0419eda5133008.png