中缀表达式构建二叉树
在上篇文章 栈结构与四则运算 中提到了通过算术表达式构造二叉树，比如
是一个标准的算术表达式，也叫 中缀表达式 。在通过中缀表达式构造二叉树的过程中，计算数要作为叶子节点，运算符作为中间节点，考虑算术优先级。因为正常单从一个中缀表达式是无法获得唯一的一个二叉树结构的。总结来说，中缀表达式构造二叉树有以下几个步骤和要点：
如下对中缀表达式 9+(3-1)*3+10/2 构造二叉树过程：
根据优先级，分为三个部分 9 , + , (3-1)*3+10/2 ，计算数9为左叶子，运算符+为中间节点；
继续分割 (3-1)*3+10/2 ，也是三部分 (3-1)*3 , + , 10/2 ，+为根节点，左子树为 (3-1)*3 ，右子树为 10/2
继续，先拆分左侧 (3-1)*3 ，三部分 3-1 , * , 3 ，* 中间节点，3右叶子，继续可以拆分 3-1 ；
拆分右侧，对于 10/2 ，拆分为 10 , / , 2 ，整个转换完成。
最终的树结构如图
中缀表达式转后缀表达式怎么转?
中缀表达式a + b*c + (d * e + f) * g，其转换成后缀表达式则为a b c * + d e * f + g * +。
转换过程需要用到栈，具体过程如下：
1）如果遇到操作数，我们就直接将其输出。
2）如果遇到操作符，则我们将其放入到栈中，遇到左括号时我们也将其放入栈中。
3）如果遇到一个右括号，则将栈元素弹出，将弹出的操作符输出直到遇到左括号为止。注意，左括号只弹出并不输出。
4）如果遇到任何其他的操作符，如（“+”， “*”，“（”）等，从栈中弹出元素直到遇到发现更低优先级的元素(或者栈为空)为止。弹出完这些元素后，才将遇到的操作符压入到栈中。有一点需要注意，只有在遇到" ) "的情况下我们才弹出" ( "，其他情况我们都不会弹出" ( "。
5）如果我们读到了输入的末尾，则将栈中所有元素依次弹出。
扩展资料
与前缀表达式（例：+ 3 4）或后缀表达式（例：3 4 +）相比，中缀表达式不容易被计算机解析，但仍被许多程序语言使用，因为它符合人们的普遍用法。
与前缀或后缀记法不同的是，中缀记法中括号是必需的。计算过程中必须用括号将操作符和对应的操作数括起来，用于指示运算的次序。
例：
（1）8+4-6*2用后缀表达式表示为：84+6 2*-
（2）2*（3+5）+7/1-4用后缀表达式表示为：235+*71/+4-
中缀表达式如何转换为前后缀表达式？
1、中缀表达式变后缀的算法：遇到操作数，直接输出。
2、栈为空是，遇到运算符，直接入栈。
3、遇到左括号时，将其入栈。
4、遇到右括号时，执行出栈操作，并且开始将出栈的元素输出。直到弹出栈的元素是左括号为止。
5、遇到其他运算符的时候，弹出所有优先级大于等于该运算符栈顶元素，然后将该运算符入栈。最终将栈中的元素依次出栈。
C语言 中缀表达式
写了个，你试试。
#include stdio.h
#define is_digit(ch) ((ch) = '0' (ch) = '9')
char pri[7][7] =
{
{'','','','','','',''},
{'','','','','','',''},
{'','','','','','',''},
{'','','','','','',''},
{'','','','','','=','$'},
{'','','','','$','',''},
{'','','','','','$','='},
};
int get_cal_index(char c)
{
switch(c)
{
case '+': return 0;
case '-': return 1;
case '*': return 2;
case '/': return 3;
case '(': return 4;
case ')': return 5;
case '#': return 6;
}
return -1;
}
int main(void)
{
char infix[200];
char suffix[200];
char cal[200];
char *np,*ip,*sp,*cp;
int nci, oci;
gets(infix);
infix[strlen(infix) +1] = ' ';
infix[strlen(infix)] = '#';
cal[0] = '#';
ip = infix;
sp = suffix;
cp = cal;
while(*ip)
{
if(is_digit(*ip))
{
int has_dot = 0;
while(is_digit(*ip) || *ip == '.')
{
*sp++ = *ip;
*sp++ = ' ';
if(*ip == '.')
{
if(has_dot)
{
printf("错误的计算数");
exit(-1);
}
has_dot = 1;
}
ip++;
}
ip--;
}
else
{
nci = get_cal_index(*ip);
if(nci == -1)
{
printf("错误的运算符");
exit(-1);
}
oci = get_cal_index(*cp);
while(pri[oci][nci] == '')
{
*sp++ = *cp--;
*sp++ = ' ';
oci = get_cal_index(*cp);
}
if(pri[oci][nci] == '')
{
*++cp = *ip;
}
else if(pri[oci][nci] == '=')
{
if(*ip == ')')
cp--;
else if(*ip == '#')
break;
}
else if(pri[oci][nci] == '$')
{
printf("错误的表达式");
exit(-1);
}
}
ip++;
}
*sp = ' ';
puts(suffix);
return 0;
}
关于中缀表达式和中缀表达式转后缀表达式栈的变化的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。