本文共 3539 字，大约阅读时间需要 11 分钟。
#pragma once#include#include #define MAXSIZE 100 #define MaxSize 128 //预先分配空间，这个数值根据实际需要预估确定typedef int ElemType;typedef struct _SqStack{ ElemType *base; //栈底指针 ElemType *top; //栈顶指针 }SqStack; bool InitStack(SqStack &S) //构造一个空栈 S { S.base = new ElemType[MaxSize];//为顺序栈分配一个最大容量为 Maxsize 的空间 if (!S.base) //空间分配失败 return false; S.top=S.base; //top 初始为 base，空栈 return true; }bool PushStack(SqStack &S, ElemType e) // 插入元素 e 为新的栈顶元素 { if (S.top-S.base == MaxSize) //栈满 return false; *(S.top++) = e; //元素 e 压入栈顶，然后栈顶指针加 1，等价于*S.top=e; S.top++; return true; } bool PopStack(SqStack & S, ElemType & e) //删除 S 的栈顶元素，暂存在变量 e 中{ if (S.base == S.top){//栈空 return false; } e = *(--S.top); //栈顶指针减 1，将栈顶元素赋给 e return true; }ElemType* GetTop(SqStack &S) //返回 S 的栈顶元素，栈顶指针不变 { if (S.top != S.base){ //栈非空 return S.top - 1; //返回栈顶元素的值，栈顶指针不变 } else{ return NULL; } }int GetSize(SqStack &S){//返回栈中元素个数 return (S.top-S.base); }bool IsEmpty(SqStack &S){//判断栈是否为空 if (S.top == S.base){ return true; }else{ return false; } }void DestoryStack(SqStack &S){//销毁栈 if(S.base){ free(S.base); S.base = NULL; S.top = NULL; } }
#include#include #include #include #include "expression.h" using namespace std; //比较 lhs 的优先级是否不高于 rhs，rhs 表示栈顶的符号 bool isLarger(const int &lhs, const int &rhs) { if ((rhs == '+' || rhs == '-') && (lhs == '*' || lhs == '/')){ return true; } return false; }int operate(int left, int right, int op)//对运算符求值 { int result = 0; cout<<"left:"< <<" right:"< << (char)op<
Calculate() 函数获得一个字符串
创建2个栈
一个存储操作数
一个存储运算符
分支语句
int status = 0; 0-接受左操作数 1-接受运算符 “±*/” 2-接受右操作数
ldata=0, 储存左操作数
rdata=0; 储存右操作数
初始化二个栈
循环遍历这个字符串
首先判断这个字符这个字符是否为空isspace函数为空返回非零的数;continue;
判断status的数值是什么
是0:接受左操作数
判断这个字符是否为操作数isdigit函数参数在0-9之间返回值为非零的数;否则为零
不为零的情况:
//第一次零10没有影响 //如果左操作数不是一位数,进入一次10,两次乘100
ldata*=10;
//把字符转换成整数,ldata累加这个数
ldata+=input[i]-‘0’;
为零的情况:
PushStack(data_stack, ldata);//ldata 入栈
//为零时: i–//这个字符已经不是一个操作数了再次遍历这个字符
i–;
status=1; //循环完这次后转到status等于1的分支
是1;1-接受运算符 “±*/”
If判断是否是+-*/字符
是的情况:
//判断是否为第一个运算符
是第一个运算符
暂时不做任何处理，运算符先入栈保存
Status=2;//转到status 等于2的分支
不是:
非第一个运算符，则与之前的运算符比较优先级
调用isLarger 函数 第一个参数:当前的运算符,第二个参数:栈中保 存的运算符(前一个运算符)
如果当前的运算符大于前一个运算符返回true;
isLarger函数返回true时
将当前的运算符入栈
Status=2;//执行完这次循环后转到status 等于2的分支
rdata=0;//rdata是右操作数重新置为零//进入这个分支这个字符就不是操作数了
IsLargar函数返回false时
/当前运算符的优先级不高于前一个运算符，则计算 前 一个运算符的值
循环条件:运算符的栈不能为空并且前一个运算符的优先级不大于当前的运算符while(){
int left=0, //保存运算符左边第二个出栈的 操作数
right = 0;//保存运算符右边首个出栈的操作数
int opt;//保存栈中的运算符
PopStack(data_stack, right);
PopStack(data_stack, left);
PopStack(opt_stack, opt);
调用operate函数计算left opt right的值
赋给 int result
//result进栈
PushStack(data_stack, result);
}
当前运算符进栈
PushStack(opt_stack, input[i]);
Status=2;//执行完这次循环后转到status 等于2的分 支
rdata=0;//rdata是右操作数重新置为零//进入这个
分支的这个字符就不是操作数了
运算符是=的情况:
循环条件:运算符的栈为空时
While(){
PopStack(data_stack, rdata); //出栈把值赋给rdata
PopStack(data_stack, ldata);//出栈把值赋给ladata
PopStack(opt_stack, opt); //
//进行运算结果赋给result
result = operate(ldata, rdata, opt); //result 入栈
PushStack(data_stack, result);
}
Return 返回result //总的结果
否则的话就 cerr<<“输入运算符错误！”<<endl;
status是2:
判断这个字符是否为操作数isdigit函数参数在0-9之间返回值为非零的数;否则为零
不为零的情况:
//第一次零10没有影响 //如果左操作数不是一位数,进入一次10,两次乘100
rdata*=10;
//把字符转换成整数,rdata累加这个数
rdata+=input[i]-‘0’;
为零的情况:
PushStack(data_stack, rdata);
//为零时: i–//这个字符已经不是一个操作数了再次遍历这个字符
i–;
status=1; //循环完这次后转到status等于1的分支
转载地址：http://lfyki.baihongyu.com/