中缀表达式就是我们平时喜闻乐见的形式:二元运算符在中间,它的两个操作数在两侧:
a + b * c + ( d * e + f ) * g
后缀和前缀表达式,顾名思义就是把运算符分别放在前面或者后面,注意没有括号,手工转换方法是按运算顺序添加括号,然后把相应的运算符置于相应的括号的前或后,如:
((a + ( b * c)) + (((d * e) + f) * g))
放到前面有:
+(+(a*(b c))*(+((*(d e))f)g))
放到后面有:
((a(b c)*)+(((d e)*f)+g)*)+
去掉括号,前缀表示式为:
++a*bc*+*defg
后缀表达式为:
abc*+de*f+g*+
很明显地可以看到他们和中缀表达式的区别在于,他们的优先级信息蕴含在式子里,不需要额外的括号,求值方法是。对于前缀表达式:
从右向左扫描式子,从右边第一个字符开始判断,如果当前字符是数字则一直到数字串的末尾再记录下来,如果是运算符,则将右边离得最近的两个“数字串”作相应的运算,以此作为一个新的“数字串”并记录下来。一直扫描到表达式的最左端时,最后运算的值也就是表达式的值。
对于后缀表达式,原理是一样的,只是读取表达式的方向相反,从左向右扫描表达式。
两种方式都很容易地用栈来实现,因此,计算机通常才用这种方式来计算
表达式树,即把表达式组织成一棵树,以操作符为根节点,操作数为叶子,递归地组织即可。容易知道,对表达式树分别进行前中后遍历即可分别得到前中后缀表达式。
中缀表达式和后缀表达式之间的转换
借助于栈,实现很简单
1、如果遇见右括号,就弹出栈中元素,直到遇到左括号
2、遇到运算符,则与栈顶的当前运算符比较。高于栈顶则入栈,否则出栈,直到栈顶运算符的优先级比它低。对于左括号,直接入栈
3、遇到操作数,则直接写到后缀表达式里。
实现如下:
int infix_to_postfix(char *in, char *post, Stack* st) { int infix_len = strlen(in), i, j; for (i = 0, j = 0; i < infix_len; i++) { if (isdigit(in[i]) || isalpha(in[i])) { post[j++] = in[i]; } else if (in[i] == '(') { push(&st, in[i]); } else if (in[i] == ')') { while (check_top(st) != '(') { post[j++] = pop(&st); } pop(&st); } else { //pop if the operator's priority is less or equal than the top while (!isempty_stack(st) && check_top(st) != '(' && get_priority(in[i]) <= get_priority(check_top(st))) { post[j++] = pop(&st); } push(&st, in[i]); } } while (!isempty_stack(st)) { post[j++] = pop(&st); } }
中缀和前缀表达式的转换
基本类似与中缀与后缀,只不过是倒序读入。并在结束后,倒序输出:
1、如果遇见左括号,就弹出栈中元素,直到遇到右括号
2、遇到运算符,则与栈顶的当前运算符比较。高于栈顶则入栈,否则出栈,直到栈顶运算符的优先级不比它低(包括相等)。对于右括号,直接入栈
3、遇到操作数,则直接写到前缀表达式里。
实现如下:int infix_to_prefix(char *in, char *pre, Stack* st) { reverse_str(in); int infix_len = strlen(in), i, j; for (i = 0, j = 0; i < infix_len; i++) { if (isdigit(in[i]) || isalpha(in[i])) { pre[j++] = in[i]; } else if (in[i] == ')') { push(&st, in[i]); } else if (in[i] == '(') { while (check_top(st) != ')') { pre[j++] = pop(&st); } pop(&st); } else { //pop if the operator's priority is less than the top while (!isempty_stack(st) && check_top(st) != ')' && get_priority(in[i]) < get_priority(check_top(st))) { pre[j++] = pop(&st); } push(&st, in[i]); } } while (!isempty_stack(st)) { pre[j++] = pop(&st); } reverse_str(pre); }
Bintree_node* postfix_to_tree (char *s, Stack* st) { char *p; int len = strlen(s), i; Bintree_node * p_node, *op1, *op2; for (p = s, i = 0; i < len; i++) { // while (*(p+i) == ' ') i++; if (isdigit(*(p+i))) { p_node = (Bintree_node*)malloc(sizeof(Bintree_node)); p_node -> ele = *(p+i); p_node -> left = NULL; p_node -> right = NULL; push(&st, p_node); } else if (*(p+i) == '+' || *(p+i) == '*' || *(p+i) == '/' || *(p+i) == '-') { op1 = pop(&st); op2 = pop(&st); p_node = (Bintree_node*)malloc(sizeof(Bintree_node)); p_node -> ele = *(p+i); p_node -> left = op2; p_node -> right = op1; push(&st, p_node); } } return pop(&st); }
原文:http://blog.csdn.net/simon_xia_uestc/article/details/37735917