输入输出示例
自定义的线性表数据结构
这是数据成员变量和部分需要用到的成员函数
1.有参构造函数new一个给定长度与类型的线性表
2.append函数将传入的值添加到线性表末尾
3.getValue返回给定下标索引的值
4.getLength返回当前线性表长度
template<class T>
class arrList {
private:
int maxSize;
T* data;
int curlen;
public:
arrList(int mSize) {
maxSize = mSize;
data = new T[maxSize];
curlen = 0;
}
~arrList() {
curlen = 0;
}
bool append(const T x) {
if (curlen >= maxSize) {
printf("表已满\n");
return false;
}
data[curlen++] = x;
return true;
}
T getValue(const int pos) {
if (pos<0 || pos>curlen - 1) {
printf("wrong position");
exit(0);
return NULL;
}
return data[pos];
}
int getLength() {
return curlen;
}
};
中缀表达式转后缀表达式
从头到尾依次扫描中缀序列mid。
1.如果为操作数，则直接输出到post序列
ps：这里需要注意数符转换的问题，因为mid中是char型数据，所以计算机按ASCII码存储。如果直接输出到post序列中计算，则是二者ASCII的值相计算，2+3实际算的是’2’+‘3’。所以这里转换一下，将每个数字字符减48，这样得到的ASCII值在读取时才能表示为真正要参与运算的值。
2.如果为开括号，则将开括号入栈。
3.如果为闭括号，则将此时栈中开括号之前的元素全部弹出到post序列
4.如果为运算符，要决定是pop弹栈还是push入栈
（1）如果栈为空，则没得弹，只能入栈
（2）如果栈顶为开括号，因为开括号要保留，所以不弹，将运算符入栈
（3）如果栈顶为运算符且运算符优先级低，则不弹，将运算符入栈
ps：在后缀表达式中，运算符靠前的先算，所以先入post的是高优先级运算符。这里如果输入运算符优先级高，也不能直接入post，因为后边的运算符优先级可能更高，或者有括号的情况，所以这里先用栈记录下来，好跟后边的比。
（4）上述三项均不满足则将栈中元素用while一直往外弹到post序列中，直到三个条件满足之一。
template<class T>
bool midToPost(arrList<char> mid, arrList<T> &post) {
stack<T> stk;
for (int i = 0; i < mid.getLength(); i++) {
T c = mid.getValue(i);
//printf("%c ", c);
if (c <= '9' && c >= '0')//遇到操作数
post.append(c - 48);
else if (c == '(')//遇到开括号
stk.push(c);
else if (c == ')') {//遇到闭括号
if (stk.empty()) {
printf("中缀表达式错误");
return false;
}
while (stk.top() != '(') {//将开括号之前都出栈
post.append(stk.top());
stk.pop();
}
stk.pop();//弹出开括号
}//else if
else {//遇到操作符
while (!stk.empty() && stk.top() != '(' && isPrior(stk.top(), c)) {
post.append(stk.top());
stk.pop();
}
stk.push(c);
}//else
}//for
while (!stk.empty()) {
post.append(stk.top());
stk.pop();
}
post.append('=');//后缀表达式结束标志
//printArr<char>(post);
return true;
}
比较运算符优先级
这个函数用于比较栈顶（第一个传参）和中缀表达式扫描到的要处理的运算符（第二个传参）优先级，如果top优先级高则返回true，否则返回false。
（这里小数点也当作运算符处理，a.b运算规则：a+0.1*b）
运算符优先级如下所示
小数点、幂运算>乘除>加减
1. 按运算符优先级检查top，如果top为最高优先级，则c优先级一定不高于top。
2. 如果top为中等优先级，则分类讨论。如果c为最高优先级，则返回false，其他返回true。
3. 如果top为最低优先级，则同样分类讨论。如果c为中等or最高优先级，则返回false，其他返回true。
template<class T>
bool isPrior(T top,char c) {
if (top == '.' || top == '^')
return true;
else if (top == '*' || top == '/') {
if (c == '.' || c == '^')
return false;
else
return true;
}
else {
if (c == '*' || c == '/' || c == '.' || c == '^')
return false;
else
return true;
}
}
后缀表达式计算
从头读取post序列。
1.遇到操作数入栈。
2.遇到运算符则从栈顶取出两个元素，与运算符计算，将计算结果压回栈中。
template<class T>
bool calPost(arrList<T> post) {
stack<double> res;
for(int i=0;post.getValue(i)!='=';i++) {
char pointer = post.getValue(i);
if (pointer < 10 && pointer >= 0) {
res.push(pointer);
}
else {
double a = res.top(); res.pop();
double b = res.top(); res.pop();
printf("%lf %c %lf = ", b,pointer, a);
switch (pointer) {
case('+'):res.push(b + a); break;
case('-'):res.push(b - a); break;
case('*'):res.push(b * a); break;
case('/'):res.push(b / a); break;
case('^'):res.push(exp(b, a)); break;
case('.'):res.push(point(b, a)); break;
default:break;
}
printf("%lf\n", res.top());
}
}//for
printf("result= %lf",double(res.top()));
return true;
}
输出
如果要输出的是数字，则将ASCII值＋48输出对应的数字。
如果要输出的符号，则直接输出。
template<class T>
void printArr(arrList<T> arr) {
for (int i = 0; i < arr.getLength(); i++) {
if (arr.getValue(i) < 9 && arr.getValue(i) > 0)
printf("%c", arr.getValue(i)+48);
else
printf("%c", arr.getValue(i));
}
printf("\n");
}
主程序
int main() {
char c = '0';
arrList<char> mid_input = arrList<char>(20);
printf("please input mid_representation:\n");
while (1) {
scanf("%c", &c);
if (c == '='||c=='\n')
break;
mid_input.append(c);
}
printf("中缀表达式:"); printArr<char>(mid_input);
arrList<char> post = arrList<char>(20);
midToPost<char>(mid_input, post);
printf("后缀表达式:"); printArr<char>(post);
calPost<char>(post);