——主要参考了中国大学MOOC数据结构课程的内容
后缀表达式：指的是不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行（不再考虑运算符的优先规则）。如果要算后缀表达式的值得话，还是比较容易的，基本的算法是：从左到右读入后缀表达式的各项，如果是运算数：就入栈；如果是运算符就从堆栈中弹出适当数量的运算数，计算并结果入栈；最后，堆栈顶上的元素就是表达式的结果值。
但我们一般使用的算是的中缀表达式，其求值基本策略：将中缀表达式转换为后缀表达式，然后求值。中缀表达式转后缀表达式的算法是：从头到尾读取中缀表达式的每个对象，对不同对象按不同的情况处理。
- 运算数：直接输出；
- 左括号：压入堆栈；
- 右括号：将栈顶的运算符弹出并输出，直到遇到左括号（出栈，不输出）；
- 运算符：若优先级大于栈顶运算符时，则把它压栈；若优先级小于等于栈顶运算符时，将栈顶运算符弹出并输出；再比较新的栈顶运算符，直到该运算符大于栈顶运算符优先级为止，然后将该运算符压栈；
- 若各对象处理完毕，则把堆栈中存留的运算符一并输出。
下面是具体的代码
#include<iostream>
#include<string.h>
#include<stack>
#include<iomanip>
#define MAX 100
using namespace std;
bool isNumber(char c) {
if(c>='0'&&c<='9') {
return true;
}
return false;
}
double readNumber(char* postfix,int& index,double& n) {
n = 0.0;
int power = 0;//power 幂
double decimal = 1.0;
bool isDecimal = false;
while(isNumber(postfix[index])||postfix[index]=='.') {
if(isNumber(postfix[index])) {
n = n*10 + postfix[index]-'0';
if(isDecimal) {
power++;
}
} else {
isDecimal = true;
}
index++;
}
for(int i=0; i<power; i++) {
decimal = decimal*0.1;
}
n = n*decimal;
}
double calculatePostfix(char* postfix) {
stack<double> st;
double n;
int index = 0;
while(postfix[index]!='\0') {
while(postfix[index]==' ') {
index++;
}
if(isNumber(postfix[index])) {
readNumber(postfix,index,n);
st.push(n);
} else if(postfix[index]=='\0') {
} else {
char c = postfix[index];
index++;
double x,y,result = 0.0;
x = st.top();
st.pop();
y = st.top();
st.pop();
switch(c) {
case '+':
result = y+x;
break;
case '-':
result = y-x;
break;
case '*':
result = y*x;
break;
case '/':
result = y/x;
break;
default:
cout<<"输入的表达式有错误！"<<endl;
return -1;
break;
}
st.push(result);
}
}
cout<<setiosflags(ios::fixed)<<setprecision(2)<<st.top()<<endl;
st.pop();
}
int getPriority(char c) {
if(c=='+'||c=='-') {
return 1;
} else if(c =='*'||c == '/') {
return 2;
} else {
return 0;
}
}
int cmp(char c1,char c2) {
if(getPriority(c1)>getPriority(c2)) {
return 1;
} else if(getPriority(c1)<getPriority(c2)) {
return -1;
} else {
return 0;
}
}
void infix2postfix(char* infix) {
char temp[MAX];
stack<char> st;
int index = 0;
int i = 0;
while(infix[index]!='\0') {
while(infix[index]==' ') {
index++;
}
if(isNumber(infix[index])||infix[index]=='.') {
while(isNumber(infix[index])||infix[index]=='.') {
temp[i++] = infix[index++];
}
temp[i++] = ' ';
} else {
switch(infix[index]) {
case '(':
st.push(infix[index++]);
break;
case ')':
infix[index++];
while(st.top()!='(') {
temp[i++] = st.top();
temp[i++] = ' ';
st.pop();
}
st.pop();
break;
case '+':
case '-':
case '*':
case '/':
if(!st.empty()) {
if(cmp(infix[index],st.top())>0) {
st.push(infix[index++]);
} else {
while(!st.empty()&&cmp(infix[index],st.top())<=0) {
temp[i++] = st.top();
temp[i++] = ' ';
st.pop();
}
st.push(infix[index++]);
}
} else {
st.push(infix[index++]);
}
break;
default:
break;
}
}
};
while(!st.empty()) {
temp[i++] = st.top();
temp[i++] = ' ';
st.pop();
}
temp[i] = '\0';
strcpy(infix,temp);
}
void calculate(char* expression) {
infix2postfix(expression);
calculatePostfix(expression);
}
int main() {
char expression[MAX];
cin.getline(expression,MAX);
calculate(expression);
return 0;
}
这个程序比我想象中要复杂，这种算法就是，你在写的时候，思维一定要清晰，不然容易忘记一些细节，而这些细节，在写的时候注意到，要比后来调试要容易一些。
这个程序不支持负数，去POJ测试过了，应该问题不大。要加上对负数的支持也比较简单。就写到这里吧。
