前面既然写了中缀转后缀的，那么现在说下中缀转前缀的，至于后缀（前缀）转中缀，可以根据相关的转换规则自行转换。
目的
将中缀表达式（即标准的表达式）转换为前缀表达式
例如：1+2*3+(4*5+6)7 转换成 ++1*23+*4567
转换原则：
与中缀转后缀不同，前者是顺序从左到右读取每一个字符，后者是从右到左顺序读取每一个字符，然后进行反转字符串。
如果遇到操作数，直接将操作数放入到prefix 中
如果遇到操作符，如果符号栈为空，直接放入符号栈中，如果符号栈不为空，则判断当前栈顶元素 
如果当前栈顶元素为右括号‘）’，直接将操作符放入符号栈中
如果当前栈顶元素的优先级大于操作数的优先级，则将栈顶元素移除，再次和判断移除后栈的栈顶元素比较优先级大小，直到当前栈顶元素小于或等于操作数优先级，将操作符放入符号栈中
如果遇到右括号，直接将右括号放入符号栈中
如果遇到左括号，将右括号到左括号之间的全部符号移出到prefix 中（记得左括号不要入栈，并且在最后将右括号从栈中删除）
重复1-4，直到最后一个字符被读入。
判断当前栈是否为空，如果不为空，将栈中的元素依次移出到prefix 中
翻转字符串
和中缀转后缀不同，进行优先级比较的时候，需要注意等号的问题
实例
首先，读入‘7’，并送到输出，然后‘*’被读入并压入栈中。接下来‘）’读入并送到栈中，此时状态如下： 
栈：*） 
输出：7
接下来读入‘6’，并送到输出，然后读入‘+’此时状态如下： 
栈：* ) + 
输出：7 6
然后读入‘5’，并送到输出，然后继续读入‘*’，由于‘*’的优先级比‘+’高，所以直接加入栈中，再将‘4’送到输出，因此状态如下： 
栈：* ) + * 
输出：7 6 5 4
下一个读入的符号‘（’，由于规则4，因此将符号栈中的操作符依次出栈，然后读入‘4’，并在最后将右括号弹出： 
栈：* 
输出： 7 6 5 4 * +
继续读入，此时读入‘+’，由优先级小于栈中‘*’的优先级，因此依照规则2，依次出栈，最后将‘+’入栈，接下来读入‘3’： 
栈：+ 
输出：7 6 5 4 * + * 3
往后读入的符号是‘*’，将‘*’入栈。然后将‘2’放入输出： 
栈：+ * 
输出：7 6 5 4 * + * 3 2
现在读入‘+’，由于符号栈中存在‘+’且它们的优先级相同，根据规则，除非，优先级大于栈顶元素，否则不出栈，依次栈中状态如下： 
栈：+ + 
输出：7 6 5 4 * + * 3 2 *
下一个读入‘1’： 
栈：+ + 
输出：7 6 5 4 * + * 3 2 * 1
现在输入为空，弹出所有栈中元素 
栈：空 
输出：7 6 5 4 * + * 3 2 * 1 + +
最后翻转 
输出：+ + 1 * 2 3 * + * 4 5 6 7
实现代码
/*
    利用栈将（中缀表达式）转换成（前缀表达式）
    e.g.
        1+2*3+(4*5+6)*7 转换成 ++1*23*+*4567

    infix（中缀表达式） : 1+2*3+(4*5+6)*7
    prefix（前缀表达式） : ++1*23*+*4567
*/
#include <algorithm>
#include <iostream>
#include <stack>
#include <string>
#include <map>
using namespace std;

void InfixToPrefix(const string infix, string& prefix)
{
    stack<char> mark;                           // 符号栈

    map<char, int> priority;                    // 符号优先级
    priority['+'] = 0;
    priority['-'] = 0;
    priority['*'] = 1;
    priority['/'] = 1;

    int infix_length = infix.size();            // 中缀表达式的字符长度
    prefix.reserve(infix_length);               // 提高效率
    for(int i = infix_length - 1; i >= 0; --i) {
        switch(infix[i]) {
            case '0':
            case '1':
            case '2':
            case '3':
            case '4':
            case '5':
            case '6':
            case '7':
            case '8':
            case '9':
                prefix.push_back(infix[i]);
                break;
            case '+':
            case '-':
            case '*':
            case '/':
                if(!mark.empty()) {
                    char markTop = mark.top();
                    // 注意此处，与中缀转后缀有所不同
                    while(markTop != ')' && priority[infix[i]] < priority[markTop]) {
                        prefix.push_back(markTop);
                        mark.pop();
                        if(mark.empty()) {
                            break;
                        }
                        markTop = mark.top();
                    }
                }
                mark.push(infix[i]);
                break;
            case ')':
                mark.push(infix[i]);
                break;
            case '(':
            {
                char markTop = mark.top();
                while(markTop != ')') {
                    prefix.push_back(markTop);
                    mark.pop();
                    markTop = mark.top();
                }
                mark.pop();
            }
                break;
        }
    }
    // 剩余的全部出栈
    while(!mark.empty()) {
        prefix.push_back(mark.top());
        mark.pop();
    }
    reverse(prefix.begin(), prefix.end());
}

int main(int argc, char const *argv[])
{
    std::string infix = "1+2*3+(4*5+6)*7";
    std::string prefix;

    cout << "infix : " << infix << endl;
    InfixToPrefix(infix, prefix);
    cout << "prefix : " << prefix << endl; 

    return 0;
}

之前总结了利用栈来将中缀表达式转为后缀与前缀表达式的规则（中缀表达式转前/后缀规则），并且附上了代码。最近复习到了树，正好使用二叉树来实现一下。
表达式树
表达式长成下面这个样子:

下图为：

后缀表达式 ：ACB*+D/ 的表达式树。

前缀表达式为：/ + A * C B D

中缀表达式为: A + C * B / D


如何构造表达式树
从左到右遍历表达式，如果遇到操作数则推入栈中，如果为操作符则将占中的操作数拿出，再以操作符为根构建一棵树，此后将刚刚构建的以操作符为根的二插入放入栈中。

步骤如下所示：

以后缀表达式 ACB*+D/为例，从左到右开始遍历，前三个都是操作， 先创建操作数节点，之后再将节点放入栈中。

如下所示:


随着遍历的执行，会遇到操作符 *(乘号)，接下来我们需要pop两次，将B和Cpop出来，以乘号为根，构建二叉树。

如下图所示:


将根节点放入栈中。


继续向后遍历，如此往复之后完成遍历。最后栈中会有一个根节点。将根节点拿出后，可以得到一整棵表达式树。

实现
//
//  Expression_Tree.c
//  Data_structure
//
//  Created by 양송 on 2020/05/30.
//  Copyright © 2020 양송. All rights reserved.
//

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

#define Stack_Size 20

typedef struct node
{
    char data;
    struct node* left;
    struct node* right;
}Bin_T;

Bin_T* Stack[Stack_Size];
int Top = -1;

int Stack_Empty()
{
    if(Top == -1)
    {
        return 1;//return empty
    }
    else
        return 0;
}

int Stack_Full()
{
    if(Top == Stack_Size-1)
    {
        return 1; // return full
    }
    else
    {
        return 0;
    }
}

void Stack_Push(Bin_T* node)
{
    if(Stack_Full())
    {
        printf("Stack full\n");
        assert(0);
    }
    else
    {
        Top++;
        Stack[Top] = node;
    }
}

Bin_T* Stack_Pop()
{
    if(Stack_Empty())
    {
        printf("Stack empty\n");
        assert(0);
    }
    else
    {
        Bin_T *node = Stack[Top];
        Top--;
        return node;
    }
}

Bin_T* create_node(Bin_T* T, char evl)
{
    T = (Bin_T*)malloc(sizeof(Bin_T));
    T->left = NULL;
    T->right = NULL;
    T->data = evl;
    return T;
}

void insert_left(Bin_T** T, Bin_T* left)
{
    if((*T) == NULL)
    {
        printf("root node is NULL\n");
        assert(0);
    }
    else
    {
        (*T)->left = left;
    }
}

void insert_right(Bin_T** T, Bin_T* right)
{
    if((*T) == NULL)
    {
        printf("root node is NULL\n");
        return;
    }
    else
    {
        (*T)->right = right;
    }
}


void Preorder(Bin_T* T)
{
    if(T == NULL)
    {
        return;
    }
    else
    {
        printf("%c ", T->data);
        Preorder(T->left);
        Preorder(T->right);
    }
}

void Inorder(Bin_T* T)
{
    if(T == NULL)
    {
        return;
    }
    else
    {
        Inorder(T->left);
        printf("%c ",T->data);
        Inorder(T->right);
    }
}

void PostOrder(Bin_T* T)
{
    if(T == NULL)
    {
        return;
    }
    else
    {
        PostOrder(T->left);
        PostOrder(T->right);
        printf("%c ", T->data);
    }
}

int main()
{
    Bin_T* T = NULL;
    char exp[] = "ACB*+D/";
    for(int i = 0; i< strlen(exp);i++)
    {
        if((exp[i] >= '1' && exp[i] <= '99') || (exp[i] >= 'A' && exp[i] <= 'Z')) //如果为操作数
        {
            Stack_Push(create_node(T, exp[i]));
        }
        else //如果部位操作数，拿出栈中前两个操作数，以操作符为根构造树
        {
            T = create_node(T, exp[i]);
            insert_right(&T, Stack_Pop());
            insert_left(&T, Stack_Pop());
            Stack_Push(T);
        }
    }
    T = Stack_Pop();
    
    printf("prefix exp: ");
    Preorder(T);
    printf("\n");
    printf("Infix exp: ");
    Inorder(T);
    printf("\n");
    printf("posftfix exp: ");
    PostOrder(T);
    printf("\n");
    
}


执行结果

中缀表达式转前/后缀表达式-利用栈(C语言）
中缀表达式转前缀表达式规则
中缀表达式转后缀表达式规则

中缀表达式转前缀表达式规则

使用两个栈，运算符栈，数字(操作数)栈.
从右到左遍历表达式.
遇到操作数时，直接放入操作数栈中. 反之,遇到运算符时，如果运算符栈为空或栈顶操作符为右括号’ )’，直接入栈，如果不为空，比较其与运算符栈顶运算符的优先级：若当前操作符优先级比栈顶运算符的较高或相等，将运算符压入运算符栈. 反之，将运算符栈顶的运算符弹出并压入到操作数栈中，再次与运算符栈顶运算符相比较；
如果是左括号“(”，则依次弹出运算符栈顶的运算符，并压入操作数栈，直到遇到右括号’)'止，此时将这一对括号丢弃.重复此步骤直到完全遍历完表达式。
如果完全遍历完表达式，运算符栈不为空,将运算符栈中剩余的运算符依次弹出并压入操作数栈中。
依次弹出操作数栈中的元素并输出，得到中缀表达式对应的前缀表达式。

中缀表达式转后缀表达式规则

使用两个栈，运算符栈，数字(操作数)栈.
从左到右遍历表达式.
遇到操作数时，直接放入操作数栈中. 反之,遇到运算符时，如果运算符栈为空或栈顶操作符为左括号’ (’，直接入栈，如果运算符栈不为空，比较其与运算符栈顶运算符的优先级：若当前操作符优先级比栈顶运算符的较高或相等，将运算符压入运算符栈. 反之，将运算符栈顶的运算符弹出并压入到操作数栈中，再次与运算符栈顶运算符相比较；
如果是左括号“)”，则依次弹出运算符栈顶的运算符，并压入操作数栈，直到遇到右括号’('止，此时将这一对括号丢弃.重复此步骤直到完全遍历完表达式。
如果完全遍历完表达式，运算符栈不为空,将运算符栈中剩余的运算符依次弹出并压入操作数栈中。
依次弹出操作数栈中的元素并输出，得到中缀表达式对应的前缀表达式。

#代码如下
//202.5.18
//written by 木有米线啊

#include <stdio.h>
#include <time.h>
#include <string.h>

#define stack_size 20

typedef struct
{
	char op_stack[stack_size];
	int op_top;
}Stack;



int get_priority(char op)
{
	switch (op)
	{
	case '+':
		return 1;
	case '-':
		return 1;
	case '*':
		return 2;
	case '/':
		return 2;
	case '(':
		return 0;
	case ')':
		return 0;
	default:
		break;
	}
}

void stack_init(Stack *s)
{
	s->op_top = -1;
}


int stack_full(Stack s)
{
	if (s.op_top == stack_size-1)
		return 1;//stack_full
	else
		return 0;
}

int stack_empty(Stack s)
{
	if (s.op_top == -1)
		return 1;//stack empty
	else
		return 0;

}

int stack_push(Stack *s,char op)
{
	if (stack_full(*s))
	{
		printf("stack full\n");
		return 0;
	}
	else
	{
		s->op_top++;
		s->op_stack[s->op_top] = op;
		return 1;
	}

}

int stack_pop(Stack *s)
{
	if (stack_empty(*s))
	{
		printf("stack empty\n");
		return 0;
	}
	else
	{
		char op = s->op_stack[s->op_top];
		s->op_top--;
		return op;
	}
}

int get_top_element(Stack s)
{
	if (stack_empty(s))
	{
		return 0;
	}
	else
	{
		return s.op_stack[s.op_top];
	}
}
void Prefix(Stack *s1, Stack *s2, char *op)
{
	int priority = 0;
	for (int i = (strlen(op)-1); i >= 0; i--)
	{
		if (op[i] == ')')//如果当前元素为左括号，直接入栈
			stack_push(s1,op[i]);
		else if (op[i] == '(')//将（之前的所有元素出栈,并写入字符串
		{
			while (1)
			{
				char ele = stack_pop(s1);
				if (ele == ')')
					break;
				else {
					stack_push(s2, ele);
					//opt[opt_index] = ele;//写入后缀字符串
					//opt_index++;
				}
			}
		}
		else if (op[i] > 'A' && op[i] < 'Z' || op[i] > 'a' && op[i] < 'z' || op[i] >= '0')
		{
			//如果当前元素不为操作符
			//opt[opt_index] = op[i];
			//opt_index++;
			stack_push(s2, op[i]);
		}
		else//剩下的既不是左右括号，也不是元素，而是操作符，需要比较优先级
		{
			if (stack_empty(*s1))
			{
				stack_push(s1,op[i]);
			}
			else
			{
				priority = get_priority(op[i]);//得到当前元素优先级
				int pri = get_priority(s1->op_stack[s1->op_top]);//得到栈顶元素优先级
				if (get_priority(op[i]) >= get_priority(get_top_element(*s1)))//如果大于等于栈顶操作符优先级，入栈
				{
					stack_push(s1, op[i]);
				}
				else//如果不是，栈顶挨个出栈，直到找出小于等于该操作符优先级的站内操作符
				{
					while (1)
					{
						//char element = stack_pop(s1);//栈顶元素依次出栈

						if (get_priority(get_top_element(*s1)) <= get_priority(op[i]) || get_top_element(*s1) == '(')//如果栈内元素的优先级小于，
						{
							stack_push(s1, op[i]);
							break;
						}
						stack_push(s2, stack_pop(s1));
						//opt[opt_index] = element;
						//opt_index++;
					}
				}
			}
		}

	}
	//字符串遍历完成后，若stack不为空，强行pop
	while (stack_empty(*s1) == 0)
	{
		char elem = stack_pop(s1);
		if (elem != ')') {
			stack_push(s2, elem);
		}

	}
	printf("Prefix expression: ");
	while (stack_empty(*s2) == 0)//打印前缀表达式
	{
		printf("%c", stack_pop(s2));
	}

	printf("\n");

}
void Postfix(Stack *s1, Stack *s2,char* op)
{
	int priority = 0;
	for (int i = 0; i < strlen(op) ; i++)
	{
		if (op[i] == '(')//如果当前元素为左括号，直接入栈
			stack_push(s1, op[i]);
		else if (op[i] == ')')//将（之前的所有元素出栈,并写入字符串
		{
			while (1)
			{
				char ele = stack_pop(s1);
				if (ele == '(')
					break;
				else {
					stack_push(s2, ele);
					//opt[opt_index] = ele;//写入后缀字符串
					//opt_index++;
				}
			}
		}
		else if (op[i] > 'A' && op[i] < 'Z' || op[i] > 'a' && op[i] < 'z' || op[i] >= '0')
		{
			//如果当前元素不为操作符
			//opt[opt_index] = op[i];
			//opt_index++;
			stack_push(s2, op[i]);
		}
		else//剩下的既不是左右括号，也不是元素，而是操作符，需要比较优先级
		{
			if (stack_empty(*s1))
			{
				stack_push(s1, op[i]);
			}
			else
			{
				//priority = //得到当前元素优先级
				//int pri = get_priority(s1->op_stack[s1->op_top]);//得到栈顶元素优先级
				if (get_priority(op[i]) >= get_priority(get_top_element(*s1)))//如果大于等于栈顶操作符优先级，入栈
				{
					stack_push(s1, op[i]);
				}
				else//如果不是，栈顶挨个出栈，直到找出小于等于该操作符优先级的站内操作符
				{
					while (1)
					{
						//char element = stack_pop(s1);//栈顶元素依次出栈

						if (get_priority(get_top_element(*s1)) <= get_priority(op[i]) || get_top_element(*s1) == '(')//如果栈内元素的优先级小于，
						{
							stack_push(s1, op[i]);
							break;
						}
						stack_push(s2, stack_pop(s1));
						//opt[opt_index] = element;
						//opt_index++;
					}
				}
			}
		}

	}
	//字符串遍历完成后，若stack不为空，强行pop
	while (stack_empty(*s1) == 0)
	{
		char elem = stack_pop(s1);
		if (elem != '(') {
			stack_push(s2, elem);
		}

	}
	int index = 0;
	int opt[50];
	while (stack_empty(*s2) == 0)//打印后缀表达式
	{
		opt[index] = stack_pop(s2);
		index++;
	}

	printf("postfix expression: ");
	for (int i = index-1; i >= 0; i--)
	{
		printf("%c", opt[i]);
	}

	printf("\n");
}

int main()
{
	char* formula;
	char op[] = "1-(2+3)";

	printf("Original expression : %s\n", &op);

	Stack s1,s2,s3,s4;
	stack_init(&s1);
	stack_init(&s2);
	stack_init(&s3);
	stack_init(&s4);
	Prefix(&s1,&s2,op);
	Postfix(&s3, &s4, op);

}

一.表达式的三种形式：  
中缀表达式：运算符放在两个运算对象中间，
如：(2+1)*3  
后缀表达式：不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行（不再考虑运算符的优先规则，
如：2 1 + 3 *  
前缀表达式：同后缀表达式一样，不包含括号，运算符放在两个运算对象的前面，
如：* + 2 1 3 
二.表达式的转换：
 
将中缀表达式转换为后缀表达式的算法思想：  
·数字时，加入后缀表达式； ·
运算符： a. 若为最低级的运算符，入栈；  
b. 若为 '('，入栈；  
c. 若为 ')'，则把栈中的的运算符加入后缀表达式中，直到 '('，从栈中删除'(' ;  
d. 若为不是最低级的运算符，则将从栈顶到第一个优先级不大于（小于，低于或等于）它的运算符（或 '(',但优先满足前一个条  
件）之间的运算符加入后缀表达式中，该运算符再入栈；
>>这句话不好理解，可以说成这样，从栈顶开始，依次弹出比当前处理的运算符优先级高的运算符，直到一个比它优先级低的或者遇到了一个左括号就停止。 ·


当扫描的中缀表达式结束时，栈中的的所有运算符出栈；  


运用后缀表达式进行计算的具体做法：  
·建立一个栈S ·
从左到右读后缀表达式，读到数字就将它转换为数值压入栈S中，读到运算符则从栈中依次弹出两个数分别到Y和X，然后以“X 运算符 Y”的形式计算机出结果，再压加栈S中
  
·如果后缀表达式未读完，就重复上面过程，最后输出栈顶的数值则为结束


三.表达式之间的转换  
这里我给出一个中缀表达式：a+b*c-(d+e)  
第一步：按照运算符的优先级对所有的运算单位加括号：式子变成拉：((a+(b*c))-(d+e))  
第二步：转换前缀与后缀表达式  
前缀：把运算符号移动到对应的括号前面  
则变成拉：-( +(a *(bc)) +(de))  
把括号去掉：-+a*bc+de 前缀式子出现  
后缀：把运算符号移动到对应的括号后面  
则变成拉：((a(bc)* )+ (de)+ )-  
把括号去掉：abc*+de+- 后缀式子出现  
发现没有，前缀式，后缀式是不需要用括号来进行优先级的确定的。


如表达式：3+(2-5)*6/3 
后缀表达式 栈
3 +
3 +(
3 2 +(-
3 2 5 - +
3 2 5 - +*
3 2 5 - 6 +*/
3 2 5 - 6 3 +*/
3 2 5 - 6 3 / * +