摘要：来实验室已经两周了，用师兄的话说，基本处于自嗨状态。张老师问C++学的怎么样了？能不能编一个简单的计算器出来？我想这个计算器肯定不能简单到只算加减乘除，于是想来想去想写一个能处理括号的计算器，最好能写个简单的UI出来。在思考过程中发现，这个计算器的难点就是如何把中缀表达式转换为后缀表达式，以及如何计算后缀表达式。
计算思路
人的思路
如果只是用于解题的话，这种方法是最快最准确的。但是它不适用于计算机。下面以a+b*c+(d*e+f)*g为例子讲以下人应该怎么把中缀表达式转换成后缀表达式。
-
按先加减后乘除的原则给表达式加括号
结果：
((a+(b*c))+(((d*e)+f)*g)) -
由内到外把每个括号里的表达式换成后缀
最终结果：
abc*+de*f+g*+
这样就得到了中缀表达式转后缀表达式的最终结果。此法应付考试有神效。
计算机的思路
毕竟计算机跟人不一样，它“笨”啊！人的思路它用不了。那么它该怎么把中缀表达式转换成后缀表达式呢？
计算机的思路需要用到栈，先来明确中缀表达式转后缀表达式的规则：
1）如果遇到操作数，我们就直接将其输出。
2）如果遇到操作符，则我们将其放入到栈中，遇到左括号时我们也将其放入栈中。
3）如果遇到一个右括号，则将栈元素弹出，将弹出的操作符输出直到遇到左括号为止。注意，左括号只弹出并不输出。
4）如果遇到任何其他的操作符，如**（“+”， “*”，“（”）**等，从栈中弹出元素直到遇到发现更低优先级的元素(或者栈为空)为止。弹出完这些元素后，才将遇到的操作符压入到栈中。有一点需要注意，只有在遇到" ) “的情况下我们才弹出” ( “，其他情况我们都不会弹出” ( "。
5）如果我们读到了输入的末尾，则将栈中所有元素依次弹出。
下面以a+b*c+(d*e+f)*g为例子来讲讲计算机的转换过程。下面在描述栈的情况是直接用文字描述了，由左到右为栈底到栈顶。空表示栈空
-
由左向右遍历表达式，首先遇到a，直接将其输出。
此时输出为：
a栈的情况为：空
-
继续遍历，遇到+，将其放入栈中。
此时输出为：
a栈的情况为：+
-
继续遍历，遇到b，直接将其输出。
此时输出为：
ab栈的情况为：+
-
继续遍历，遇到*，因为*的优先级大于栈顶的+，所以将*放入栈内。
此时输出为：
ab栈的情况为：+*
-
继续遍历，遇到c，直接将其输出。
此时输出为：
abc栈的情况为：+*
-
继续遍历，遇到+，因为+的优先级低于栈顶的*，故将*弹出；然后新的栈顶元素的+与这个+优先级相同，故也要弹出现在栈顶的+；然后栈空了，将现在这个+放入栈中。
此时输出为：
abc*+栈的情况为：+
-
继续遍历，遇到(，直接将其放入栈中，不遇到)不会将(弹出。
此时输出为：
abc*+栈的情况为：+(
-
继续遍历，遇到d，直接将其输出。
此时输出为：
abc*+d栈的情况为：+(
-
继续遍历，遇到*，因为栈顶为(,不遇到)不将(弹出,故直接将*放入栈中。
此时输出为：
abc*+d栈的情况为：+(*
-
继续遍历，遇到e，直接将其输出。
此时输出为：
abc*+de栈的情况为：+(*
-
继续遍历，遇到+，因为+比栈顶*的优先级低，故将*弹出；新的栈顶元素为(,不遇到)不弹出(,故将+放入栈中。
此时输出为：
abc*+de*栈的情况为：+(+
-
继续遍历，遇到f，直接将其输出。
此时输出为：
abc*+de*f栈的情况为：+(+
-
继续遍历，遇到),直接将栈中元素依次弹出并输出直到遇到(为止，注意：(弹出但不输出。
此时输出为：
abc*+de*f+栈的情况为：+
-
继续遍历，遇到*，因为*的优先级大于栈顶元素+的优先级，故直接将*入栈。
此时输出为：
abc*+de*f+栈的情况为：+*
-
继续遍历，遇到g，直接将其输出。
此时输出为：
abc*+de*f+g栈的情况为：+*
-
继续遍历，为空，遍历结束。将栈内元素依次弹出。
此时输出为：
abc*+de*f+g*+栈的情况为：空
至此，中缀表达式转后缀已经全部完成，结果为abc*+de*f+g*+。
代码实现
源代码
代码是用C++写的，不过还是用的面向过程的思路。代码如下：
//中缀表达式转后缀
#include<iostream>
#include<string>
#include<stack>
using namespace std;
int prio(char op) { //给运算符优先级排序
int priority;
if (op == '*' || op == '/')
priority = 2;
if (op == '+' || op == '-')
priority = 1;
if (op == '(')
priority = 0;
return priority;
}
bool Trans(string &str,string &str1) { //引用传递
stack<char> s; //定义一个char类型的栈s
int i;
for (i = 0; i<str.size(); i++) {
if (str[i] >= '0' && str[i] <= '9') { //如果是数字，直接入栈
str1+=str[i];
}
else { //否则不是数字
if (s.empty()) //栈空则入站
s.push(str[i]);
else if (str[i] == '(') //左括号入栈
s.push(str[i]);
else if (str[i] == ')') { //如果是右括号，只要栈顶不是左括号，就弹出并输出
while (s.top() != '(') {
str1+= s.top();
s.pop();
}
s.pop(); //弹出左括号，但不输出
}
else {
while (prio(str[i]) <= prio(s.top())) { //栈顶优先级大于等于当前运算符，则输出
str1+= s.top();
s.pop();
if (s.empty()) //栈为空，停止
break;
}
s.push(str[i]); //把当前运算符入栈
}
}
}
while (!s.empty()) { //最后，如果栈不空，则弹出所有元素并输出
str1+= s.top();
s.pop();
}
return true;
}
int main() { //主程序
string infix;
string postfix;
cout << "请输入中缀表达式：" << infix << endl;
cin >> infix;
Trans(infix,postfix);
cout << "后缀表达式为：" << postfix << endl;
return 1;
}
程序测试
这里我们就用a+b*c+(d*e+f)*g的实例1+2*3+(4*5+6)*7来测试我们的程序，可见运行结果为123*+45*6+7*+，计算正确。
总结
在写这段小程序时有一些不小的收获。毕竟是一个初学者，犯的错误都是很低级的知识性错误，理解不到位，基础不扎实。这里要感谢我的本科同学白洋耐心地教我。
1）string类的对象在没有初始化大小的情况下不要用其下标运算，会出现string subscript out of range（下标越界）的错误。在第三次执行循环时出现，大概是因为string对象的默认大小为2个字节。
2）string类的对象不以’\0’结尾，要与C语言区分开来，判断其结束时用size()函数。size() 函数返回的是其大小，然后下标是以0开始的，所以最大到size-1。
3）函数调用进行形实结合时要用引用传递。
4）#include<stack>的使用。
京公网安备 11010502036488号