网站建设分享文章,企业在线查询,百度网站是用什么软件做的,免费的cms视频网站模拟栈
题目链接 栈的数组模拟非常简单#xff0c;不详细描述 设置一个指针指向栈顶第一个元素即可 STL中stack实现已经更新在STL_Stack #includeiostream
#includestringusing namespace std;const int N1e51;
int m;
string s;
int stack[N];
int p;//指针…模拟栈
题目链接 栈的数组模拟非常简单不详细描述 设置一个指针指向栈顶第一个元素即可 STL中stack实现已经更新在STL_Stack #includeiostream
#includestringusing namespace std;const int N1e51;
int m;
string s;
int stack[N];
int p;//指针,指向栈顶元素 int main(){cinm;p0;//刚开始p0说明栈内为空 while(m--){cins;if(spush){int x;cinx;stack[p]x;}else if(spop){p--;}else if(sempty){if(p0)coutYES\n;elsecoutNO\n;}else if(squery){coutstack[p]\n;}}return 0;
}表达式求值 思路 关于表达式求值详解可见bilibili视频讲解 需要设置一个符号栈、一个数字栈 其中数字栈比较简单只要扫描到数字直接入栈即可 对于符号栈要注意若是空栈或者当前是左括号符号直接可以进 每次扫描到符号想入栈时如果扫描的符号优先级大于当前栈顶的元素那么可以直接入栈想象成优先级高的可以压住优先级低的但是如果平级即和、-和-这样的那么就不能入栈需要将符号栈中元素不断pop出直到能压住或者栈空毕竟符号优先级相同谁都不服谁那么先入栈的先出去吧 如果有符号出栈那么就立即将其和数字栈中的数字组合求得的值再次压入数字栈中 直到所有元素都被扫描完然后把符号栈中的元素清理干净即可 实现代码
具体思路在代码中写的很清楚了 #includeiostream
#includestring
#includealgorithm
#includestack
#includeunordered_mapusing namespace std;stack int num_s;//数字栈
stack char ope_s;//运算符栈
unordered_map char,int h {{,1},{-,1},{*,2},{/,2}};//定义优先级映射集 void eval(){//计算、当有符号出栈时将其和数字栈中的元素结合计算//此时注意元素在栈中的顺序因为对于除法来说a/b和b/a不一样 int a,b;//两个需要被运算的数字 char ope;//运算符 //第二个数字 bnum_s.top();num_s.pop();//第一个数字 anum_s.top();num_s.pop();//运算符opeope_s.top();ope_s.pop(); //进行运算int result;if(ope)resultab;if(ope-)resulta-b;if(ope*)resulta*b;if(ope/)resulta/b;//将计算结果压入栈中 num_s.push(result); }int main(){string s;cins;//读取表达式 for(int i0;is.size();i){//从头扫描表达式 if(isdigit(s[i])){//isdigit()用于判断该元素是否为数字int ji,x0;//因为数字可能为多位数因此需要用while读取并且将字符串中的字符转为int以此用于计算 while(js.size()isdigit(s[j])){xx*10s[j]-0;j;}//读取完就将其放入栈中num_s.push(x);//此时j指向一个操作符由于循环结束时i会,因此这里需要将i的值设为j-1//这样在i后下一次循环扫描的就是操作符了 ij-1;}else if(s[i](){//如果是左括号可以直接压入栈ope_s.push(s[i]); }else if(s[i])){//如果是右括号那么就要将左右括号中间所有的操作符弹出并计算while(ope_s.top()!(!ope_s.empty()){//当栈顶不为(且不为空 eval();//计算计算的时候会自动pop符号 } //最后要把( pop出去ope_s.pop(); }else{//如果是操作符那么就要判断操作符和栈顶元素优先级while(!ope_s.empty()h[ope_s.top()]h[s[i]]){//如果当前扫描的元素不比栈顶元素大那么就要eval弹出栈顶元素直到s[i]能压住栈顶元素 eval();} //如果扫描元素能够压住栈顶元素那么直接入栈ope_s.push(s[i]); }} //扫描完了处理符号栈中剩余元素while(!ope_s.empty()){eval();} coutnum_s.top()endl;return 0;
}
