数据结构 - 拓展突破（C++实现中缀表达式转前缀表达式，中缀表达式转后缀表达式，前缀表达式求值，中缀表达式求值）

1. C++中缀表达式转后缀表达式

输入中缀表达式样例:
2+48+(88+1)/3

输出后缀表达式样例:
248*+88*1+3/+

对于中缀表达式转换为后缀表达式，我们需要用以下步骤来解决这个问题：

1. 初始化一个栈：运算符栈st
2. 从左往右开始扫描中缀表达式
   • 遇到数字，直接输出
   • 遇到运算符：
     • 若为 ‘(’ 直接入栈
     • 若为 ‘)’ 将符号栈中的元素依次出栈并输出，直到 ‘(’, ‘(’ 只出栈，不输出
     • 若为其他符号，将符号栈中的元素依次出栈并将其输出，直到遇到比当前符号优先级更低的符号或者 ‘(’。

//首先定义优先级
#include 
#include 
#include 

using namespace std;

int priority(const char ch)
{
    // */优先级相同最大
    int priority = 0;
    if (ch == '*' || ch == '/')
        priority = 2;
    else if (ch == '+' || ch == '-')
        priority = 1;
    else if (ch == '(')
        priority = 0;
    else
        //其他字符优先级错误
        priority = -1;
    return priority;
}

string turnPostfix(string &str)
{
    stack<char> st;
    string ret; //保存中缀转后缀的结果
    for (int i = 0; i < str.size(); i++)
    {
        // cout << str[i] << endl;

        //如果这个字符没有优先级，说明这个字符不是操作符
        if (priority(str[i]) == -1 && str[i] != ')')
        {
            //字符直接输出
            ret.push_back(str[i]);
        }
        else
        {
            if (st.empty())
            {
                st.push(str[i]);
            }
            else
            {
                //如果str[i]==）将栈输出，直到（
                if (str[i] == ')')
                {
                    while (st.top() != '(')
                    {
                        ret.push_back(st.top());
                        st.pop();
                    }
                    //将（弹出栈
                    st.pop();
                }
                else
                {
                    //如果是(直接入栈
                    if (str[i] == '(')
                    {
                        st.push(str[i]);
                    }
                    else
                    {
                        //将优先级大于这个操作符的字符出栈输出
                        //cout << "INFO:" << st.top() << endl;
                        while (!st.empty() && priority(st.top()) >= priority(str[i]))
                        {
                            ret.push_back(st.top());
                            st.pop();
                        }
                        //将这个操作符号入栈
                        st.push(str[i]);
                    }
                }
            }
        }
    }
    //将栈剩下的元素全部出栈
    while (!st.empty())
    {
        ret.push_back(st.top());
        st.pop();
    }
    return ret;//调用string的拷贝构造函数返回
}

int main()
{
    //string input = "2+4*8+(8*8+1)/3";
    string input = "a*(b+c)-d";
    cout << turnPostfix(input) << endl;
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

2. C++中缀表达式转前缀表达式

整体思路正好于后缀相反

输入中缀表达式：(a+b) * (c+d)

输出前缀表达式为： * ,+,a,b,+,c,d。

1. 初始化一个运算符栈st

2. 从右至左扫描中缀表达式，从右边第一个字符开始判断。

   • 遇到数字直接输出
   • 如果是运算符，则比较优先级。如果当前运算符的优先级大于等于栈顶运算符的优先级则将运算符直接入栈；否则将栈顶运算符 出栈并输出，直到当前运算符的优先级大于等于栈顶运算符的优先级，再将这个运算符入栈（当栈顶是括号时，直接入栈）
     • 如果是括号，则根据括号的方向进行处理。如果是右括号，则直接入栈；否则，遇左括号前将所有的运算符全部出栈并输出，并将左右括号删除
       -最后将字符串逆转就是前缀表达式

//首先定义优先级
#include 
#include 
#include 
#include 

using namespace std;

int priority(const char ch)
{
    // */优先级相同最大
    int priority = 0;
    if (ch == '*' || ch == '/')
        priority = 2;
    else if (ch == '+' || ch == '-')
        priority = 1;
    else if (ch == ')')
        priority = 0;
    else
        //其他字符优先级错误
        priority = -1;
    return priority;
}

string turnPrefix(const string &str)
{
    string ret;
    stack<char> st;
    for (int i = str.length() - 1; i >= 0; i--)
    {
        // cout << str[i] << " " << endl;
        if (priority(str[i]) == -1 && str[i] != '(')
        {
            //数字,直接输出到ret上即可
            ret.push_back(str[i]);
        }
        else
        {
            if (str[i] == '(')
            {
                //弹出栈，直到遇到)
                while (st.top() != ')')
                {
                    ret.push_back(st.top());
                    st.pop();
                }
                //将')'弹出栈
                st.pop();
            }
            else
            {
                if (st.empty())
                {
                    st.push(str[i]);
                }
                else
                {
                    if (str[i] == ')')
                    {
                        //右括号直接入栈
                        st.push(str[i]);
                    }
                    else
                    {
                        //栈优先级大的出栈
                        while (!st.empty() && priority(st.top()) > priority(str[i]))
                        {
                            ret.push_back(st.top());
                            st.pop();
                        }
                        //将这个操作符入栈
                        st.push(str[i]);
                    }
                }
            }
        }
    }
    while (!st.empty())
    {
        ret.push_back(st.top());
        st.pop();
    }

    std::reverse(ret.begin(), ret.end());
    return ret;
}

int main()
{
    string input = "1+((2+3)*4)-5";
    cout << turnPrefix(input) << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

3. C++后缀表达式求值

1. 准备一个数字栈。从左到右扫描后缀表达式
2. 如果是数字，放入数字栈。
3. 如果是符号，从数字栈中弹出两个数字，第一个取出的数字为右运算数，第二个为左运算数，进行运算。然后将结果放进数字栈中。
4. 如此反复，直到读完整个表达式后，留在数字栈中的那个数字就是最终结果。

#include 
#include 
#include 
#include 
#include 

using namespace std;

//传入后缀表达式
int PostfixToNumber(const string &str)
{
    std::map<char, std::function<int(int, int)>> opMap ={
            {'+', [](int x, int y){ return x + y; }},
            {'-', [](int x, int y){ return x - y; }},
            {'*', [](int x, int y){ return x * y; }},
            {'/', [](int x, int y){ return x / y; }},
    };

    stack<int> st;
    for (int i = 0; i < str.length(); i++)
    {
        if (str[i] >= '0' && str[i] <= '9')
        {
            st.push(str[i] - '0');
        }
        else
        {
            int right = st.top();
            st.pop();
            int left = st.top();
            st.pop();
            //实际上就是switch case 不同的运算符执行不同的运算，我这里使用C++11包装器
            st.push(opMap[str[i]](left,right));
        }
    }
    return st.top();
}

int main()
{
    //"2+4*8+(8*8+1)/3"
    cout<<PostfixToNumber("248*+88*1+3/+")<<endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

4. C++前缀表达式求值

1. 创建一个数字栈

2. 从右至左扫描表达式，从右边第一个字符开始判断如果当前字符(或字符串)为数字或变量，则直接压入数字栈内；如果是运算符，则弹出两个数字运算；如此反复，直到读完整个表达式；

需要注意：

	后缀表达式右值为第一个栈顶元素，左值为第二个栈顶元素
	前缀左值为第一个栈顶元素，右值为第二个栈顶元素
1
2

#include 
#include 
#include 
#include 
#include 

using namespace std;

//传入前缀表达式
int PrefixToNumber(const string &str)
{
    std::map<char, std::function<int(int, int)>> opMap ={
            {'+', [](int x, int y){ return x + y; }},
            {'-', [](int x, int y){ return x - y; }},
            {'*', [](int x, int y){ return x * y; }},
            {'/', [](int x, int y){ return x / y; }},
    };
    stack<int> st;
    for (int i = str.length() - 1; i >= 0; i--)
    {
        if (str[i] >= '0' && str[i] <= '9')
        {
            st.push(str[i] - '0');
        }
        else
        {
            int left = st.top();
            st.pop();
            int right = st.top();
            st.pop();
            st.push(opMap[str[i]](left,right));
        }
    }
    return st.top();
}

int main()
{
    //1+((2+3)*4)-5 
    cout<<PrefixToNumber("-+1*+2345")<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

---

Github地址（2023考研数据结构实操，大题代码）

参考博客：

栈的应用之前、中、后缀表达式（C++）

前缀表达式和后缀表达式 - C++代码

【PTA】后缀表达式 （中缀表达式转化为后缀表达式）