将中缀表达式转换为表达式树

参考：

思路

8-(3+5)*(5-6/2) 
怎样把中缀表达式转为二叉树？中缀表达式的括号怎样处理？
一般情况下并不能由一个中缀表达式得到一个唯一的二叉树，但是若由二叉树来表示表达式，叶子节点必须是操作数，非叶子节点是操作符，所以能够确定一个二叉树：转化过程如下：
按照优先级加上括号，得到：( 8 - ( (3 + 5) * ( 5 - (6 / 2) ) ) ) 
然后从最外层括号开始，依次转化成二叉树 
1、根是- ，左子树8，右子树( (3 + 5) * ( 5 - (6 / 2) ) ) 
2、右子树的根*，右子树的左子树(3 + 5)，右子树的右子树( 5 - (6 / 2) ) 
3、(3 + 5)的根+，左子树3 ，右子树5 
4、( 5 - (6 / 2) )的根-，左子树5，右子树(6 / 2) 
5、(6 / 2)的根/，左子树6，右子树2 后序遍历此二叉树能够得到该表达式的后缀（逆波兰）表示形式

代码：

#include "stdio.h"  
#include "string.h"  
#include "stdlib.h"  
#include "stack"  
using namespace std;

const char str[] = "3*4+5-2/1";

struct tree
{
char c;
struct tree* left;
struct tree* right;
};
stack<struct tree*> subTreeStack;
stack<char> operatorStack;


struct tree*  BuildTree()
{

struct tree* node;
for (unsigned int pos = 0; pos < strlen(str); pos++)
{
if (str[pos] - '0' >= 0 && str[pos] - '0' <= 9)    //若是数字则作为叶子节点  
{

node = (struct tree*) malloc(sizeof(struct tree));
node->c = str[pos];
node->left = NULL;
node->right = NULL;

subTreeStack.push(node);
}
else if (str[pos] == '*' || str[pos] == '/' || str[pos] == '+' || str[pos] == '-')
{
if (!operatorStack.empty() && (str[pos] == '+' || str[pos] == '-'))  //若优先级比栈顶元素低  
{
node = (struct tree*) malloc(sizeof(struct tree));
node->c = operatorStack.top();
node->right = subTreeStack.top();
subTreeStack.pop();
node->left = subTreeStack.top();
subTreeStack.pop();

subTreeStack.push(node);


operatorStack.pop();
operatorStack.push(str[pos]);
}
else
operatorStack.push(str[pos]);
}


}


while (!operatorStack.empty())
{

node = (struct tree*) malloc(sizeof(struct tree));
node->c = operatorStack.top();
operatorStack.pop();
node->right = subTreeStack.top();
subTreeStack.pop();
node->left = subTreeStack.top();
subTreeStack.pop();

subTreeStack.push(node);

}
return subTreeStack.top();

}
void PrintTree(struct tree* node)
{
if (node == NULL)
return;
PrintTree(node->left);

PrintTree(node->right);
printf("%c", node->c);
}


void main()
{
struct tree* root = BuildTree();
PrintTree(root);
}

在程序中，利用2个栈，高优先级的符号必然要优先运算，最终会出现在最底端，而低优先级的符号最后运算，所以出现在树的最高处。因此，在遇到“+”或者“-”符号的时候，要先将前面的“*”或者“/”计算。考虑到操作数最终会成为叶子节点。