栈的应用表达式树：

中缀表达式代码实现，另加扩展中缀转后缀表达式代码实现

原题链接： https://www.acwing.com/problem/content/description/3305/

这是我手绘图解：

中缀表达式

#include<iostream>
#include<cstring>
#include<stack>
#include<unordered_map>
using namespace std;
//num里面存放着运算结果以及运算的数
//op里面存放着操作符
stack<int> num;
stack<char> op;
//eval()计算目前的表达式的值
void eval()
{
    //注意因为用的是栈，所以先去出来的是b,其次是a，防止加减法出现负数
    auto b = num.top(); num.pop();
    auto a = num.top(); num.pop();
    auto c = op.top(); op.pop();
    int x;
    if(c == '+') x = a + b;
    else if(c == '-') x = a - b;
    else if(c == '*') x = a * b;
    else x = a/b;
    num.push(x);
}

int main()
{
    unordered_map<char,int> pr{{'+',1},{'-',1},{'*',2},{'/',2}};
    string str;
    cin>>str;
    for(int i = 0;i < str.size();i ++)
    {
        auto c = str[i];
        //倘若这个字符是数字 且 连续出现数字，那么就需要将数字字符组合起来形成一个数
        if(isdigit(c))
        {
            int x = 0, j = i;
            while(isdigit(str[j]) && j < str.size())
                x = x * 10 + str[j++] - '0';
            i = j - 1;//更新i的值
            num.push(x);
        }
        //倘若是左括号，那么就要入操作符
        else if(c == '(')   op.push(c);
        //若是右操作符，那么直到做操作符里所有的数，都要进行一系列的运算
        else if(c == ')')
        {
            while(op.top() != '(')  eval();
            op.pop();//且将左括号删除
        }
        //若操作的是+-/*操作符，则根据栈头与目前操作符比较大小，若栈头操作符大于等于目前操作符则进行计算
        //且将当前运算符入栈
        else
        {
            while(op.size() && pr[op.top()] >= pr[c])   eval();
            op.push(c);
        }
    }
    //将剩余的运算符进行计算
    while(op.size())    eval();
    cout<<num.top()<<endl;
    return 0;
}

中缀表达式 转 后缀表达式写法

#include<iostream>
#include<cstring>
#include<stack>
#include<unordered_map>
using namespace std;
//num里面存放着运算结果以及运算的数
//op里面存放着操作符
stack<int> num;
stack<char> op;
//eval()计算目前的表达式的值
void eval()
{
    auto c = op.top(); op.pop();
    cout << c << ' ';
}

int main()
{
    unordered_map<char,int> pr{{'+',1},{'-',1},{'*',2},{'/',2}};    //哈希存储<key,value>
    string str;
    cin>>str;
    for(int i = 0;i < str.size();i ++)
    {
        auto c = str[i];
        //倘若这个字符是数字 且 连续出现数字，那么就需要将数字字符组合起来形成一个数
        if(isdigit(c))
        {
            int x = 0, j = i;
            while(isdigit(str[j]) && j < str.size())    //从字符串中从左往右还原整型 1000
                x = x * 10 + str[j++] - '0';
            i = j - 1;//更新i的值
            cout << x << ' ';
        }
        //倘若是左括号，那么就要入操作符
        else if(c == '(')   op.push(c);
        //若是右操作符，那么直到做操作符里所有的数，都要进行一系列的运算
        else if(c == ')')
        {
            while(op.top() != '(')  eval();
            op.pop();//且将左括号删除
        }
        //若操作的是+-/*操作符，则根据栈头与目前操作符比较大小，若栈头操作符大于等于目前操作符则进行计算
        //且将当前运算符入栈
        else
        {
            while(op.size() && pr[op.top()] >= pr[c])   eval();
            op.push(c);
        }
    }
    //将剩余的运算符进行计算
    while(op.size())    eval();
    return 0;
}

这里我再补充一点表达式的朴素转换法：

#include<iostream>
#include<string.h>
using namespace std;

typedef struct
{
    char s[310];
    int top;
}Stack;

int weight(char ch,int flag)
{
    if(ch == '+' || ch == '-')return 1;
    if(ch == '*' || ch == '/')return 2;
    /*flag用于判别是否为栈内符号*/
    if(ch == '(' && flag == 1)return 0;
    if(ch == '(' && flag == 0)return 3;
}

void transform(char str[])
{
    /*初始化栈*/
    Stack a;
    a.top = -1;
    int i,f = 0,m = strlen(str);
    cout<<"转换后:"<<endl;
    for(i = 0;i < m;i ++)
    {
        /*筛选字母*/
        if(str[i] >= 'A' && str[i] < 'Z' || str[i] >= 'a' && str[i] < 'z')
        {
            cout<<str[i]<<" ";
        }
        else
        {
            /*若栈为空,就先入栈*/
            if(a.top == -1)
            {
                a.s[++ a.top] = str[i];
                continue;
            }
            /*若为')'则从栈顶开始打印直到'('为止*/
            if(str[i] == ')')
            {
                while(a.top != -1 && a.s[a.top] != '(')
                    cout<<a.s[a.top --]<<" ";
                a.top --;
                continue; 
            }
            /*跟栈顶符号比较优先级*/ 
            if(weight(str[i],0) > weight(a.s[a.top],1))
            {
                a.s[++ a.top] = str[i];
                continue;
            }
            /*每次进行出栈操作时都要判断栈是否为空,而且,判断在操作之前*/
            while(a.top != -1 && weight(str[i],0) <= weight(a.s[a.top],1))
            {
                /*用while循环为不用if语句来比较新读入的操作符与栈顶操作的权值大小*/
                cout<<a.s[a.top]<<" ";
                /*是因为当新读入的操作符的权值小于栈定操作符的权值时,也可能小于栈顶*/
                a.top --;
                /*下一个操作符的权值*/
                f = 1;
            }
            if(f)
            {
                a.s[++a.top] = str[i];
                f = 0;
            }
        }
    }
    while(a.top != -1)
    {
        cout<<a.s[a.top--];
    }
}


int main()
{
    char str[310];
    cout<<"请输入中缀表达式:"; 
    cin>>str;
    transform(str);
    return 0;
}
/*
中缀表达式转换为后缀表达式（思路）
1.创建栈
2.从左向右顺序获取中缀表达式
a.数字直接输出
b.运算符
情况一：遇到左括号直接入栈，遇到右括号将栈中左括号之后入栈的运算符全部弹栈输出，
        同时左括号出栈但是不输出。
情况二：遇到乘号和除号直接入栈，直到遇到优先级比它更低的运算符，依次弹栈。
情况三：遇到加号和减号，如果此时栈空，则直接入栈，否则，将栈中优先级高的运算符依次弹栈
        （注意：加号和减号属于同一个优先级，所以也依次弹栈）直到栈空或则遇到左括号为止，停止弹栈。
        （因为左括号要匹配右括号时才弹出）。
情况四：获取完后，将栈中剩余的运算符号依次弹栈输出
例:比如将:2*(9+6/3-5)+4转化为后缀表达式 2 9 6 3 / +5 -  * 4 +
————————————————
*/