中缀->后缀

先对中缀表达式按运算优先次序加上括号，再把操作符后移到右括号的后面并以就近移动为原则，最后将所有括号消去。

中缀->前缀

先对中缀表达式按运算优先次序通统加上括号，再把操作符前移到左括号前并以就近移动为原则，最后将所有括号消去。

代码实现中缀转为后缀

原理：

  • isp叫做栈内(in stack priority)优先数
  • icp叫做栈外(in coming priority)优先数。
  • icp>isp则入栈；icp<isp则出栈、输出；icp=isp只出栈 (的栈外优先级最高，一来即入栈；入栈后优先级极低，这样其他操作符可以入栈。
  • 其他操作符进入栈后优先级升1，这样可以保证相同优先级的从左到右计算。
  • 优先级相同:( )  # #

算法：

  1. 操作符栈初始化，将结束符‘#’进栈。然后读入中缀表达式字符流的首字符ch。
  2. 重复执行以下步骤，直到ch = ‘#’，同时栈顶的操作符也是‘#’，停止循环。

循环过程：

  1. 若ch是操作数直接输出，读入下一个字符ch。
  2. 若ch是操作符，判断ch的优先级icp和位于栈顶的操作符op的优先级isp：
    • 若 icp(ch) > isp(op)，ch入栈，读入下一个字符ch。
    • 若 icp(ch) < isp(op)，出栈、输出,ch继续比较。
    • 若 icp(ch) == isp(op)，出栈、不输出，读入下一个字符ch。
  3. 算法结束，输出序列即为所需的后缀表达式。

代码实现：

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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#include <iostream>

using namespace std;
class steak;
class StackNode
{
    friend class LinkedStack;

public:
    StackNode *link;
    char data;

public:
    StackNode(StackNode *ptr = NULL)
    {
        link = ptr;
    }
    StackNode(char &c, StackNode *ptr = NULL)
    {
        data = c;
        link = ptr;
    }
};
class LinkedStack
{ //链式栈类定义
public:
    StackNode *top; //栈顶指针
public:
    LinkedStack(); //构造函数
    void getTop(char &ch);
    void Push(char &ch); //进栈
    int Pop(char &ch);   //退栈
    void makeEmpty();    //清空栈的内容
    int IsEmpty() { return (top == NULL) ? 1 : 0; }
};
LinkedStack::LinkedStack()
{
    top = NULL;
}
void LinkedStack::getTop(char &ch)
{
    ch = top->data;
}
void LinkedStack::makeEmpty()
{
    if (top != NULL)
    {
        StackNode *p = top->link;
        while (top != NULL)
        { //逐个结点释放
            p = top;
            top = top->link;
            delete p;
        }
    }
}
void LinkedStack::Push(char &ch)
{
    top = new StackNode(ch, top); //创建新结点
}

int LinkedStack::Pop(char &ch)
{
    //删除栈顶结点, 返回被删栈顶元素的值。
    if (IsEmpty())
        return 0;       //栈空返回
    StackNode *p = top; //暂存栈顶元素
    top = top->link;    //退栈顶指针
    ch = p->data;
    delete p; //释放结点
    return 1;
}
int isp(char &c)
{
    //返回栈内优先级
    if (c == '#')
    {
        return 0;
    }
    else if (c == '(')
    {
        return 1;
    }
    else if (c == ')')
    {
        return 6;
    }
    else if (c == '+'  c == '-')
    {
        return 3;
    }
    else
    {
        return 5;
    }
}
int icp(char &c)
{
    //返回栈外优先级
    if (c == '#')
    {
        return 0;
    }
    else if (c == '(')
    {
        return 6;
    }
    else if (c == ')')
    {
        return 1;
    }
    else if (c == '+'  c == '-')
    {
        return 2;
    }
    else
    {
        return 4;
    }
}
void postfix() //把中缀表达式e转换成后缀表示并输出
{
    LinkedStack S;
    char ch = '#', ch1, op;
    S.Push(ch);
    cin.get(ch);
    while (!S.IsEmpty())
    {
        if (isdigit(ch))
        {
            cout << ch;
            cin.get(ch);
        }
        else
        {
            S.getTop(ch1);
            if (icp(ch) > isp(ch1))
            {
                S.Push(ch);
                cin.get(ch);
            }
            else if (icp(ch) < isp(ch1))
            {
                S.Pop(op);
                cout << op;
            }
            else
            {
                S.Pop(op);
                if (op == '(')
                    cin.get(ch); //相等，此时ch为’)’ ，op=‘(‘ 或者#(准备结束)；
            }
        }
    }
}
int main()
{
    postfix();
    return 0;
}