题目
这是NOJ中的一道题目，要求将中缀表达式转化为逆波兰式，题目描述如下：
- 假设表达式由单字母变量和双目四则运算算符构成。试编写程序，将一个通常书写形式且书写正确的表达式转换为逆波兰式。
- input (a+b)*c
- output ab+c*
分析
这道题目已经有成熟的算法了，我只是把算法实现了一遍。算法思路如下：
这道题应用了栈的结构。有原始表达式expBef，和空白的表达式expAft。在操作前，先给原始表达式的前后加上”#”。每次从原始表达式中读取一个字符icp。如果字符是字母的话，就放入expAft中；如果是符号的话就从读取栈中的top元素为isp，并用isp与icp进行比较，比较的结果查下表得：
比较的结果为三种情况：
- isp > icp:栈顶元素出栈入expAft中，并且icp不变
- isp < icp:将icp压入栈中
- isp = icp:栈顶元素出栈，且不入expAft
按此操作，直到将原始表达式读取完，并且栈中原素取完。
解决
代码实现如下，我直接在元素插入队列的时候将其输出了：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
using namespace std;
// define the operation
// '1' == '>' , '-1' == '<' , '0' == '='
int opeartor[7][7] = { { 1, 1, -1, -1, -1, 1, 1 },
{ 1, 1, -1, -1, -1, 1, 1 },
{ 1, 1, 1, 1, -1, 1, 1 },
{ 1, 1, 1, 1, -1, 1, 1 },
{ -1, -1, -1, -1, -1, 0, 0 },
{ 1, 1, 1, 1, 0, 1, 1 },
{ -1, -1, -1, -1, -1, 0, 0 } };
// change char to int for using the "opeartor"
int char2int(char aim)
{
if (aim == '+')
return PLUS;
else if (aim == '-')
return MINUS;
else if (aim == '*')
return MUL;
else if (aim == '/')
return DIVISION;
else if (aim == '(')
return LEFT;
else if (aim == ')')
return RIGHT;
else if (aim == '#')
return POUSI;
}
// judge the char is letter or not
bool isLetter(char aimChar)
{
if ((aimChar >= 'a' && aimChar <= 'z') ||
(aimChar >= 'A' && aimChar <= 'Z'))
return true;
else
return false;
}
// compete the isp and the icp
int competition(int num1, int num2)
{
return opeartor[num1][num2];
}
// change the expression to ReversePolishNotation
int changeExp(string expBef, char* expAft)
{
stack<char> operStack;
int lenExp = expBef.size();
char isp_char;
char icp_char;
int isp_int = 0;
int icp_int = 0;
int compeRes = 0;
int instrtIndex = 0;
int loop = 0;
expBef += "#";
operStack.push('#');
while (loop <= lenExp)
{
icp_char = expBef[loop];
isp_char = operStack.top();
if (isLetter(icp_char))
{
expAft[instrtIndex++] = icp_char;
cout << expAft[instrtIndex-1] ;
loop++;
}
else
{
isp_int = char2int(isp_char);
icp_int = char2int(icp_char);
compeRes = competition(isp_int, icp_int);
if (compeRes == -1)
{
operStack.push(icp_char);
loop++;
}
else if (compeRes == 1)
{
expAft[instrtIndex++] = operStack.top();
cout << expAft[instrtIndex - 1] ;
operStack.pop();
}
else if (compeRes == 0)
{
operStack.pop();
loop++;
}
}
}
return instrtIndex;
}
int main()
{
string expreBef;
char expreAft[1000];
int lenAte = 0;
cin >> expreBef;
lenAte = changeExp(expreBef, expreAft);
return 0;
}
小结
这道题的思路虽然清晰，但是实现算法的时候也有一些需要注意的细节。