5.栈的应用
程序员文章站
2024-03-22 23:35:10
...
5.1 栈求解汉诺塔问题
递归版
#include<iostream>
using namespace std;
void moveC(int n,char from,char to){
cout<<n<<" From: "<<from<<"-> "<<to<<endl;
}
void honoi(int n,char first,char second,char third){
if(n==1) moveC(1,first,third);
else{
honoi(n-1,first,third,second);
moveC(n,first,third);
honoi(n-1,second,first,third);
}
}
int main()
{
int n=4;
honoi(n,'A','B','C');
return 0;
}
非递归版(调用自己写的栈)
#include<iostream>
#include"Stack.h"
using namespace std;
void moveC(int n,char from,char to){
cout<<n<<" From: "<<from<<"-> "<<to<<endl;
}
struct HonoiState{
int n;
char A;
char B;
char C;
HonoiState(){};//构造函数,必须写
HonoiState(int ns,char first,char second,char third){
n=ns;A=first;B=second;C=third;
}
};
void solve(){
Stack<HonoiState> s;
int num=3;
s.push(HonoiState(num,'A','B','C'));
while(s.length>0){//不为空
HonoiState p=s.pop();
//s.pop();
int n=p.n;
char A=p.A,B=p.B,C=p.C;
if(n==1) {
moveC(1,A,C);
}
else{
s.push(HonoiState(n-1,B,A,C));
s.push(HonoiState(1,A,B,C));
s.push(HonoiState(n-1,A,C,B));
}
}
}
int main()
{
solve();
return 0;
}
5.2 栈求解出队序列问题
#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
// input: 输入序列，i 表示输入到第 i 个，N 表示有 N 个输入元素； seq: 某一个输出序列； result : 存储所有的序列
void GetAllSequence(const int* input, int i, const int N, stack<int> &stk, vector<int> &seq,vector<vector<int> > &result) {
if (i == N) {
// 输入序列全部入栈完毕，只能出栈。将栈中的元素添加到seq 的后面, 保存 seq
if (!stk.empty()) {
int top = stk.top();
seq.push_back(top);
stk.pop();
GetAllSequence(input, i, N, stk, seq, result); // 保持 i == N，递归地将 stk 元素复制到 seq
stk.push(top); //回溯
seq.pop_back();
} else {
result.push_back(seq); // 保存结果
}
} else {
// 对于一个输入元素，可以入栈；可以不入，弹出栈中已有元素
// 入栈
stk.push(input[i]);
GetAllSequence(input, i+1, N, stk, seq, result); // 向 i+1 递归
stk.pop(); // 回溯，恢复栈之前的状态
// 出栈
if (!stk.empty()) {
int top = stk.top(); //记录
stk.pop();
seq.push_back(top);
GetAllSequence(input, i, N, stk, seq, result); // 保持 i 不变
seq.pop_back(); // 回溯，恢复栈和序列之前的状态
stk.push(top);
}
}
}
int main()
{
int input[] = {1,2,3}; // 输入序列
const int N = sizeof(input)/sizeof(input[0]);
vector<vector<int> > result; //保存所有序列
vector<int> seq;
stack<int> stk;
GetAllSequence(input, 0, N, stk, seq, result);
for (int i = 0; i < result.size(); i++) {
for (int j = 0; j < result[0].size(); j++) {
cout << result[i][j] << " ";
}
cout << endl;
}
}
5.3 检测出栈序列是否合法
https://blog.csdn.net/liufangbaishi2014/article/details/51141623
于栈有一个很有用的性质，对于出栈序列的每一个元素，该元素后 比该元素先入栈的一定按照降序排列。若入栈的是一串数字例如12345，则21435是一个合法的出栈顺序，每一个元素i后比i小的都是降序排列（因为入栈的数字代表了进栈先后），24153不是合法的，因为对于4，比它小的1和3的顺序不对。
#include <iostream>
#include <string>
using namespace std;
int main()
{
string s1, s2;
while (cin >> s1 >> s2)
{
int n = s1.size();
int a1[n], a2[n]; //把字母转换成数字处理
for (int i = 0; i < n; ++i)
{
a1[i] = i;
a2[i] = s1.find(s2[i]);
}
int min; bool existless, islegal;
for (int i = 0; i < n; ++i)
{
min = a2[i];
existless = 0;
int j;
for (j = i + 1; j < n; ++j)
if (a2[j] < a2[i]) //是否存在比a[i]小的值
{
min = a2[j];
existless = 1;
break;
}
islegal = 1;
if (existless)
{
for (int k = j + 1; k < n; ++k)
if (a2[k] < a2[i])
{
if (a2[k] < min)
min = a2[k]; //更新min
else
{
islegal = 0;
break;
}
}
}
if (!islegal)
{ printf("NO\n"); break; }
}
if (islegal)
printf("YES\n");
}
system("pause");
return 0;
}
5.3 计算中缀表达式的值并转为后缀表达式
#include "Stack.h"//基于之前写的类模板Vector
#include<cstdio>
#include<ctype.h>
#include<cstring>
#include<cmath>
#include"Stack.h"
using namespace std;
#define N_OPTR 9 //运算符总数
typedef enum
{
ADD, SUB, MUL, DIV, POW, FAC, L_P, R_P, EOE,
} Operator; //运算符集合
//加、减、乘、除、乘方、阶乘、左括号、右括号、起始符与终止符
const char pri[N_OPTR][N_OPTR] =
{ //运算符优先等级 [栈顶] [当前]
/* |-------------------- 当 前 运 算 符 --------------------| */
/* + - * / ^ ! ( ) \0 */
/* -- + */ '>', '>', '<', '<', '<', '<', '<', '>', '>',
/* | - */ '>', '>', '<', '<', '<', '<', '<', '>', '>',
/* 栈 * */ '>', '>', '>', '>', '<', '<', '<', '>', '>',
/* 顶 / */ '>', '>', '>', '>', '<', '<', '<', '>', '>',
/* 运 ^ */ '>', '>', '>', '>', '>', '<', '<', '>', '>',
/* 算 ! */ '>', '>', '>', '>', '>', '>', ' ', '>', '>',
/* 符 ( */ '<', '<', '<', '<', '<', '<', '<', '=', ' ',
/* | ) */ ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ',
/* -- \0 */ '<', '<', '<', '<', '<', '<', '<', ' ', '='
};
void readNumber(char*& p, Stack<double>& stk)
{ //将起始于p的子串解析为数值，并存入操作数栈
stk.push((double)(*p - '0')); //当前数位对应的数值进栈
while (isdigit(*(++p))) //只要后续还有紧邻的数字（即多位整数的情况），则
{
stk.push(stk.pop() * 10 + (*p - '0')); //弹出原操作数并追加新数位后，新数值重新入栈
}
if ('.' != *p)
{
return; //此后非小数点，则意味着当前操作数解析完成
}
float fraction = 1; //否则，意味着还有小数部分
while (isdigit(*(++p))) //逐位加入
{
stk.push(stk.pop() + (*p - '0') * (fraction /= 10)); //小数部分
}
}
void append(char*& rpn, double opnd)
{ //将操作数接至RPN末尾
char buf[64];
if (0.0 < opnd - (int)opnd)
{
sprintf(buf, "%f \0", opnd); //浮点格式，或
}
else
{
sprintf(buf, "%d \0", (int)opnd); //整数格式
}
rpn = (char*)realloc(rpn, sizeof(char) * (strlen(rpn) + strlen(buf) + 1)); //扩展空间
strcat(rpn, buf); //RPN加长
}
void append(char*& rpn, char optr)
{ //将运算符接至RPN末尾
int n = strlen(rpn); //RPN当前长度（以'\0'结尾，长度n + 1）
rpn = (char*)realloc(rpn, sizeof(char) * (n + 3)); //扩展空间
sprintf(rpn + n, "%c ", optr);
rpn[n + 2] = '\0'; //接入指定的运算符
}
Operator optr2rank(char op)
{ //由运算符转译出编号
switch (op)
{
case '+':
{
return ADD; //加
}
case '-':
{
return SUB; //减
}
case '*':
{
return MUL; //乘
}
case '/':
{
return DIV; //除
}
case '^':
{
return POW; //乘方
}
case '!':
{
return FAC; //阶乘
}
case '(':
{
return L_P; //左括号
}
case ')':
{
return R_P; //右括号
}
case '\0':
{
return EOE; //起始符与终止符
}
default:
{
exit(-1); //未知运算符
}
}
}
char orderBetween(char op1, char op2) //比较两个运算符之间的优先级
{
return pri[optr2rank(op1)][optr2rank(op2)];
}
__int64 facI(int n)
{
__int64 f = 1;
while (n > 1)
{
f *= n--;
}
return f;
} //阶乘运算（迭代版）
double calcu(double a, char op, double b)
{ //执行二元运算
switch (op)
{
case '+':
{
return a + b;
}
case '-':
{
return a - b;
}
case '*':
{
return a * b;
}
case '/':
{
if (0 == b)
{
exit(-1);
}
else
{
return a / b; //注意：如此判浮点数为零可能不安全
}
}
case '^':
{
return pow(a, b);
}
default:
{
exit(-1);
}
}
}
double calcu(char op, double b)
{ //执行一元运算
switch (op)
{
case '!':
{
return (double)facI((int)b); //目前仅有阶乘，可照此方式添加
}
default:
{
exit(-1);
}
}
}
double evaluate(char* S, char*& RPN)
{ //对（已剔除白空格的）表达式S求值，并转换为逆波兰式RPN
Stack<double> opnd;
Stack<char> optr; //运算数栈、运算符栈 /*DSA*/任何时刻，其中每对相邻元素之间均大小一致
char* expr = S;
optr.push('\0'); //尾哨兵'\0'也作为头哨兵首先入栈
while (!optr.empty())
{ //在运算符栈非空之前，逐个处理表达式中各字符
if (isdigit(*S))
{ //若当前字符为操作数，则
readNumber(S, opnd);
append(RPN, opnd.top()); //读入操作数，并将其接至RPN末尾
}
else //若当前字符为运算符，则
{
switch (orderBetween(optr.top(), *S))
{ //视其与栈顶运算符之间优先级高低分别处理
case '<': //栈顶运算符优先级更低时
{
optr.push(*S); S++; //计算推迟，当前运算符进栈
break;
}
case '=': //优先级相等（当前运算符为右括号或者尾部哨兵'\0'）时
{
optr.pop(); S++; //脱括号并接收下一个字符
break;
}
case '>':
{ //栈顶运算符优先级更高时，可实施相应的计算，并将结果重新入栈
char op = optr.pop(); append(RPN, op); //栈顶运算符出栈并续接至RPN末尾
if ('!' == op)
{ //若属于一元运算符
double pOpnd = opnd.pop(); //只需取出一个操作数，并
opnd.push(calcu(op, pOpnd)); //实施一元计算，结果入栈
}
else
{ //对于其它（二元）运算符
double pOpnd2 = opnd.pop(), pOpnd1 = opnd.pop(); //取出后、前操作数 /*DSA*/提问：
//可否省去两个临时变量？
opnd.push(calcu(pOpnd1, op, pOpnd2)); //实施二元计算，结果入栈
}
break;
}
default:
{
exit(-1); //逢语法错误，不做处理直接退出
}
}
}
}
return opnd.pop(); //弹出并返回最后的计算结果
}
char* removeSpace ( char* s )
{ //剔除s[]中的白空格
char* p = s, *q = s;
while ( true )
{
while (isspace(*q))
{
q++;
}
if ( '\0' == *q )
{
*p = '\0';
return s;
}
*p++ = *q++;
}
}
//教材实例代码包中的测试用例
//值得注意的是这里所使用的测试用例需要在VS2019中点击属性然后手动设置命令参数
/*
int main(int argc, char* argv[])
{ //表达式求值（入口）
for (int i = 1; i < argc; i++)
{ //逐一处理各命令行参数（表达式）
system("cls");
printf("\nPress any key to evaluate: [%s]\a\n", argv[i]);
getchar();
char* rpn = (char*)malloc(sizeof(char) * 1);
rpn[0] = '\0'; //逆波兰表达式
double value = evaluate(removeSpace(argv[i]), rpn); //求值
printf("EXPR\t: %s\n", argv[i]); //输出原表达式
printf("RPN\t: [ %s]\n", rpn); //输出RPN
printf("Value\t= %f = %d\n", value, (int)value); //输出表达式的值
free(rpn);
rpn = NULL;
getchar();
}
system("pause");
return 0;
}
*/
int main()
{
char* rpn = (char*)malloc(sizeof(char) * 1);
rpn[0] = '\0'; //逆波兰表达式
double value = evaluate(const_cast < char*>("(1+2^3!-4)*(5!-(6-(7-(89-0!))))"), rpn); //求值
cout << value << endl;
cout << "the rpn is:" << rpn;
free(rpn);
rpn = NULL;
system("pause");
return 0;
}
5.4 计算相对分子质量
链接：https://ac.nowcoder.com/acm/problem/219040
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
string str;
map<string , ll > mp;
void slove(){
ll ans = 0;
int rear = 0;
ll st[5050] = {0}; //模仿stack
str = str+"#"; //防止下标越界处理
for(int i=0;i<str.length();i++){
if(str[i]==')'){//若字符串为左括号
//(Aa2Ab2)10 //这种情况
ll sum=0;//当栈中元素不为空时，依次相加，直到匹配到左括号
while(st[rear]!=-1)sum+=st[rear--]; rear--;
ll num = 0;
while(str[i+1]>='0'&&str[i+1]<='9') i++,num=num*10+str[i]-'0';
//将右边的系数匹配到左边的相对分子量
if(!num) num=1;//如果是0，将系数
st[++rear] = sum*num;
}else if(str[i]=='('){
st[++rear] = -1; //放个flag将左括号入栈
}else if(str[i]>='A'&&str[i]<='Z'){//将元素取出，元素最长为两个
string s = "";
s = s+str[i];
if(str[i+1]>='a'&&str[i+1]<='z') i++,s+=str[i];
ll num = 0;
//Aa25 这种情况
while(str[i+1]>='0'&&str[i+1]<='9') i++,num=num*10+str[i]-'0';
if(!num) num = 1;
st[++rear] = num*mp[s];//将相对分子量入栈
}
}
while(rear) ans+=st[rear--]; //所有的求和
cout<<ans<<endl;
}
int main(){
cin>>m>>n;
string s; ll x;
while(m--){
cin>>s>>x;mp[s] = x;
}
while(n--){
cin>>str; slove();
}
return 0;
}
5.5 检测化学方程式是否配平
CCF计算机软件能力认证试题练习：201912-3 化学方程式
解题思路
首先要清楚系数出现位置的三种情况：
1、整个化学式的首部
2、元素的右部
3、右括号的右部
如32Ba((OH)2(CO3)2)3（暂不考虑化学式的合法性）
我们从系数入手，在第一种情况下，该系数作用于化学式中的所有元素；在第二种情况下，该系数作用于紧接着的左边的元素；在第三种情况下，该系数作用于紧接着的左边的匹配括号里的所有元素，请通过上例理解。
为此，我们考虑使用一个数组将化学式的各部分存储起来arr，实现逻辑如下：
1、顺序遍历化学式
2、计算系数的第1种情况，也就是整个化学式的系数factor，继续遍历。
3、遇到左或右括号时，将左或右括号加入到arr中；遇到大写字母时，获取元素名称，将元素名称加入到arr中；遇到数字时，不存到arr中，根据系数的第2、3种情况相应处理（第1种情况已经在第二步处理完成）。
4、对于系数的第2种情况，此时数组arr的最后一个元素就是元素名称，系数作用于它即可；对于系数的第3种情况，从数组尾部逆序遍历，直到遇到左括号，将系数作用于这个范围中的元素，同时要将这一对匹配括号从数组中删除。
至此处理化学式的过程结束。
对于整个化学方程式，将其从等号两边分开处理。使用两个map分别记录左右两边的元素个数，再进行比较。
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<string>
#include<sstream>
#include<map>
#include<vector>
using namespace std;
struct Elem{ //元素
string name; //名称
int num; //个数
Elem(string _name, int _num): name(_name), num(_num){}
};
int toNumber(string str, int &pos){ //从str的pos位置开始，得到一个数字
int num=0;
while(isdigit(str[pos])){
num=num*10+str[pos]-'0';
pos++;
}
return num;
}
void calc(string &str, map<string, int> &mp){
stringstream ss(str);
string item;
while(getline(ss, item, '+')){ //获取每一个化学式，如 32Ba((OH)2(CO3)2)3
vector<Elem> arr; //存储化学式的分解序列， 如 Ba、(、(、O、H、)、(、C、O、)、)
int factor=1; //整个化学式的系数，默认为1
int i=0;
if(isdigit(item[i])) factor=toNumber(item,i); //计算化学式系数
while(i<item.size()){
if(isdigit(item[i])){ //处理数字
int num=toNumber(item,i);
if(arr[arr.size()-1].name==")"){ //序列最后一个元素是右括号
int j=arr.size()-1;
arr[j].name="*"; //将右括号标记为*，忽略它的存在
while(arr[--j].name!="("){
arr[j].num*=num;
}
arr[j].name="*"; //将左括号标记为*，忽略它的存在
}
else arr[arr.size()-1].num*=num; //序列最后一个元素是元素名称
}
else if(item[i]=='('){ //处理左括号
arr.push_back(Elem("(", 0)); //括号加入到序列中
i++;
}
else if(item[i]==')'){ //处理右括号
arr.push_back(Elem(")", 0)); //括号加入到序列中
if(i+1==item.size() || !isdigit(item[i+1])) item.insert(i+1,"1"); //考虑到右括号右边可能不出现数字，补充底数1
i++;
}
else if(isupper(item[i])){ //处理大写字母
//得到元素名称
string name="";
name+=item[i]; //大写字目
i++;
if(islower(item[i])){ //小写字母
name+=item[i];
i++;
}
arr.push_back(Elem(name,1)); //名称加入到序列中
}
}
for(int i=0; i!=arr.size(); ++i){ //将“元素->个数”保存到map中
if(arr[i].name=="*") continue; //忽略序列中括号的存在
mp[arr[i].name]+=arr[i].num*factor;
}
}
}
bool judge(map<string, int> &left, map<string, int> &right){ //判断两个map是否相同
if(left.size()!=right.size()) return false;
for(map<string, int>::iterator it=left.begin(); it!=left.end(); ++it){
if(right[it->first]!=it->second) return false;
}
return true;
}
int main(){
int n;
scanf("%d", &n);
for(int i=0; i<n; ++i){
map<string, int> left, right;
string str, lstr, rstr;
cin>>str;
stringstream ss(str);
getline(ss, lstr,'='); //得到等号左边的字符串
getline(ss, rstr); //得到等号右边的字符串
calc(lstr, left); //计算左字符串
calc(rstr, right);
if(judge(left, right)) cout<<"Y"<<endl;
else cout<<"N"<<endl;
}
return 0;
}
5.6 非递归实现组合型枚举
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
using namespace std;
vector<int> chosen;
int top, address, sta[100010], n, m;
inline void call(int x, int ret_addr) { //模拟系统栈指令call()，记录每个状态的参数和返回语句位置
int pre = top;
sta[++top] = x; //当前选择的数
sta[++top] = ret_addr; //当前执行的指令
sta[++top] = pre; //前面的容量
}
inline int ret() { //模拟指令return，退栈并返回应该执行的下一条语句
int ret_addr = sta[top - 1];
top = sta[top];
return ret_addr;
}
int main() {
cin >> n >> m;
call(1, 0); //n个整数选择m个
//操作0
//操作1
//操作2
while (top) { //如果栈不为空
int x = sta[top - 2];
switch (address) {
case 0:
if (chosen.size() > m || chosen.size() + (n - x + 1) < m) {
address = ret(); //如果此时选择的数
continue;
}
if (x == n + 1) {
for (int i = 0; i < chosen.size(); ++i)
printf("%d ", chosen[i]);
puts("");
address = ret();
continue;
}
chosen.push_back(x);
call(x+1, 1); //入栈下一个状态
address = 0; //下一个函数从头执行
continue;
case 1:
chosen.pop_back();//弹出尾部元素
call(x+1, 2); //入栈下一个状态
address = 0;
continue;
case 2:
address = ret(); //当前状态已执行完毕，返回
}
}
return 0;
}
5.7 求值算法
#include "Stack.h"//基于之前写的类模板Vector
#include<cstdio>
#include<ctype.h>
#include<cstring>
#include<cmath>
#include"Stack.h"
using namespace std;
#define N_OPTR 9 //运算符总数
typedef enum
{
ADD, SUB, MUL, DIV, POW, FAC, L_P, R_P, EOE,
} Operator; //运算符集合
//加、减、乘、除、乘方、阶乘、左括号、右括号、起始符与终止符
const char pri[N_OPTR][N_OPTR] =
{ //运算符优先等级 [栈顶] [当前]
/* |-------------------- 当 前 运 算 符 --------------------| */
/* + - * / ^ ! ( ) \0 */
/* -- + */ '>', '>', '<', '<', '<', '<', '<', '>', '>',
/* | - */ '>', '>', '<', '<', '<', '<', '<', '>', '>',
/* 栈 * */ '>', '>', '>', '>', '<', '<', '<', '>', '>',
/* 顶 / */ '>', '>', '>', '>', '<', '<', '<', '>', '>',
/* 运 ^ */ '>', '>', '>', '>', '>', '<', '<', '>', '>',
/* 算 ! */ '>', '>', '>', '>', '>', '>', ' ', '>', '>',
/* 符 ( */ '<', '<', '<', '<', '<', '<', '<', '=', ' ',
/* | ) */ ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ',
/* -- \0 */ '<', '<', '<', '<', '<', '<', '<', ' ', '='
};
void readNumber(char*& p, Stack<double>& stk)
{ //将起始于p的子串解析为数值，并存入操作数栈
stk.push((double)(*p - '0')); //当前数位对应的数值进栈
while (isdigit(*(++p))) //只要后续还有紧邻的数字（即多位整数的情况），则
{
stk.push(stk.pop() * 10 + (*p - '0')); //弹出原操作数并追加新数位后，新数值重新入栈
}
if ('.' != *p)
{
return; //此后非小数点，则意味着当前操作数解析完成
}
float fraction = 1; //否则，意味着还有小数部分
while (isdigit(*(++p))) //逐位加入
{
stk.push(stk.pop() + (*p - '0') * (fraction /= 10)); //小数部分
}
}
void append(char*& rpn, double opnd)
{ //将操作数接至RPN末尾
char buf[64];
if (0.0 < opnd - (int)opnd)
{
sprintf(buf, "%f \0", opnd); //浮点格式，或
}
else
{
sprintf(buf, "%d \0", (int)opnd); //整数格式
}
rpn = (char*)realloc(rpn, sizeof(char) * (strlen(rpn) + strlen(buf) + 1)); //扩展空间
strcat(rpn, buf); //RPN加长
}
void append(char*& rpn, char optr)
{ //将运算符接至RPN末尾
int n = strlen(rpn); //RPN当前长度（以'\0'结尾，长度n + 1）
rpn = (char*)realloc(rpn, sizeof(char) * (n + 3)); //扩展空间
sprintf(rpn + n, "%c ", optr);
rpn[n + 2] = '\0'; //接入指定的运算符
}
Operator optr2rank(char op)
{ //由运算符转译出编号
switch (op)
{
case '+':
{
return ADD; //加
}
case '-':
{
return SUB; //减
}
case '*':
{
return MUL; //乘
}
case '/':
{
return DIV; //除
}
case '^':
{
return POW; //乘方
}
case '!':
{
return FAC; //阶乘
}
case '(':
{
return L_P; //左括号
}
case ')':
{
return R_P; //右括号
}
case '\0':
{
return EOE; //起始符与终止符
}
default:
{
exit(-1); //未知运算符
}
}
}
char orderBetween(char op1, char op2) //比较两个运算符之间的优先级
{
return pri[optr2rank(op1)][optr2rank(op2)];
}
__int64 facI(int n)
{
__int64 f = 1;
while (n > 1)
{
f *= n--;
}
return f;
} //阶乘运算（迭代版）
double calcu(double a, char op, double b)
{ //执行二元运算
switch (op)
{
case '+':
{
return a + b;
}
case '-':
{
return a - b;
}
case '*':
{
return a * b;
}
case '/':
{
if (0 == b)
{
exit(-1);
}
else
{
return a / b; //注意：如此判浮点数为零可能不安全
}
}
case '^':
{
return pow(a, b);
}
default:
{
exit(-1);
}
}
}
double calcu(char op, double b)
{ //执行一元运算
switch (op)
{
case '!':
{
return (double)facI((int)b); //目前仅有阶乘，可照此方式添加
}
default:
{
exit(-1);
}
}
}
double evaluate(char* S, char*& RPN)
{ //对（已剔除白空格的）表达式S求值，并转换为逆波兰式RPN
Stack<double> opnd;
Stack<char> optr; //运算数栈、运算符栈 /*DSA*/任何时刻，其中每对相邻元素之间均大小一致
char* expr = S;
optr.push('\0'); //尾哨兵'\0'也作为头哨兵首先入栈
while (!optr.empty())
{ //在运算符栈非空之前，逐个处理表达式中各字符
if (isdigit(*S))
{ //若当前字符为操作数，则
readNumber(S, opnd);
append(RPN, opnd.top()); //读入操作数，并将其接至RPN末尾
}
else //若当前字符为运算符，则
{
switch (orderBetween(optr.top(), *S))
{ //视其与栈顶运算符之间优先级高低分别处理
case '<': //栈顶运算符优先级更低时
{
optr.push(*S); S++; //计算推迟，当前运算符进栈
break;
}
case '=': //优先级相等（当前运算符为右括号或者尾部哨兵'\0'）时
{
optr.pop(); S++; //脱括号并接收下一个字符
break;
}
case '>':
{ //栈顶运算符优先级更高时，可实施相应的计算，并将结果重新入栈
char op = optr.pop(); append(RPN, op); //栈顶运算符出栈并续接至RPN末尾
if ('!' == op)
{ //若属于一元运算符
double pOpnd = opnd.pop(); //只需取出一个操作数，并
opnd.push(calcu(op, pOpnd)); //实施一元计算，结果入栈
}
else
{ //对于其它（二元）运算符
double pOpnd2 = opnd.pop(), pOpnd1 = opnd.pop(); //取出后、前操作数 /*DSA*/提问：
//可否省去两个临时变量？
opnd.push(calcu(pOpnd1, op, pOpnd2)); //实施二元计算，结果入栈
}
break;
}
default:
{
exit(-1); //逢语法错误，不做处理直接退出
}
}
}
}
return opnd.pop(); //弹出并返回最后的计算结果
}
char* removeSpace ( char* s )
{ //剔除s[]中的白空格
char* p = s, *q = s;
while ( true )
{
while (isspace(*q))
{
q++;
}
if ( '\0' == *q )
{
*p = '\0';
return s;
}
*p++ = *q++;
}
}
int main()
{
char* rpn = (char*)malloc(sizeof(char) * 1);
rpn[0] = '\0'; //逆波兰表达式
double value = evaluate(const_cast < char*>("(1+2^3!-4)*(5!-(6-(7-(89-0!))))"), rpn); //求值
cout << value << endl;
cout << "the rpn is:" << rpn;
free(rpn);
rpn = NULL;
system("pause");
return 0;
}
5.8 地图着色(模拟栈)
#include<iostream>
#include<stdio.h>
using namespace std;
#define N 7 //地图区域数量
#define M 4//最多允许使用颜色的数量
bool maps[][N]{//注意该矩阵是对称矩阵
{0,1,1,1,1,1,0},
{1,0,0,0,0,1,0},
{1,0,0,1,1,0,0},
{1,0,1,0,1,1,0},
{1,0,1,1,0,1,0},
{1,1,0,1,1,0,0},
{0,0,0,0,0,0,0}
};
int color[N+2];//着色栈
const char* colorName[6] = { " ","紫","黄","红","绿" };
bool anyConflict(int r)//检查是否撞色
{
for(int i=0;i<N;i++){
if(maps[r-1][i]&&color[i+1]==color[r]){
return true;
}
}
return false;//返回不冲突
}
void fillColor()
{
int i=1;//考虑栈顶指针
color[i]=1;//第一个节点的元素入栈
while(i>0&&i<=N){//当节点未染色完成时
while(color[i]<=M){//当前颜色在范围内
if(!anyConflict(i)){//如果当前节点颜色不冲突,考虑下一个节点
i++;
if(i<=N)//如果下一节点合法
color[i]=1;
break;
}
color[i]++;
}
if(color[i]>M){//如果尝试M种颜色都不行
i--;
color[i]++;//更换上一节点的颜色
}
}
//cout<<"here"<<endl;
if(i>N){//如果找到着色方案
printf("找到着色方案\n");
for(int j=1;j<=N;j++){
printf("当前节点 %d 选取颜色 %d\n",j,color[j]);
}
}
else{
printf("该地图不存在仅用 %d 种颜色着色的方案\n");
}
}
int main()
{
fillColor();
return 0;
}
5.9 地图着色(栈实现)
#include<iostream>
#include<stdio.h>
#include"Stack.h"
using namespace std;
#define N 7 //地图区域数量
#define M 4//最多允许使用颜色的数量
bool maps[][N]{//注意该矩阵是对称矩阵
{0,1,1,1,1,1,0},
{1,0,0,0,0,1,0},
{1,0,0,1,1,0,0},
{1,0,1,0,1,1,0},
{1,0,1,1,0,1,0},
{1,1,0,1,1,0,0},
{0,0,0,0,0,0,0}
};
const char* colorName[6] = { " ","紫","黄","红","绿" };
struct CraphNode{
int index;//定义节点位置
int color;//定义节点颜色
CraphNode(){//构造函数
index=0;
color=0;
}
CraphNode(int a,int b){
index=a;
color=b;
}
};
bool anyConflict(CraphNode e,Stack<CraphNode> &stk)//怎么检查栈中元素是否和栈中元素撞色了呢？
{
//依次遍历栈，查看待插入元素是否和栈中元素冲突
Stack<CraphNode> tmp;//建立临时栈
int flag=0;//标志位，标志为 1 表示冲突
while(!stk.empty()){
CraphNode tsp=stk.top();//获取头节点
stk.pop();//删除头结点
tmp.push(tsp);//压入临时栈
if(maps[tsp.index-1][e.index-1]==1&&tsp.color==e.color){//如果两点相通,且颜色相同
//cout<<"here"<<endl;
//cout<<"here"<<tsp.index<<" "<<e.index<<" "<<e.color<<endl;
flag=1;
}
}
while(!tmp.empty()){//将栈还原
CraphNode tsp=tmp.top();//获取头节点
tmp.pop();//删除头结点
stk.push(tsp);
}
if(flag==1){
return true;//返回冲突
}
return false;//返回不冲突
}
void fillColor()
{
Stack<CraphNode> S;//定义地图节点栈
CraphNode head=CraphNode(1,1);
S.push(head);
//cout<<head.index<<" "<<head.color<<endl;
while(!S.empty()&&S.top().index<=N){//当栈不为空且节点染色未完成时
CraphNode tmp=S.top();//取栈顶元素
//cout<<S.top().index<<endl;
while(tmp.color<=M){//栈顶元素与前面入栈的元素不冲突
if(!anyConflict(tmp,S)){//如果当前节点颜色不冲突,考虑下一个节点
//S.push(tmp);//将当前节点重新入栈
if(tmp.index+1<=N+1){//如果下一节点合法
CraphNode tmp23=CraphNode(tmp.index+1,1);
S.push(tmp23);//节点入栈
}
break;
}
//如果当前位置颜色节点有冲突,尝试下一个颜色
tmp.color++;
S.pop();//修改当前节点的颜色
S.push(tmp);//将当前节点重新入栈
}
if(tmp.color>M){//如果尝试M种颜色都不行
//更换新栈顶节点的颜色
S.pop();//删除先有的节点
CraphNode tmp34=S.top();
S.pop();
tmp34.color++;
S.push(tmp34);
}
}
if(S.tops>N){//如果找到着色方案
printf("找到着色方案\n");
S.pop();//删除尾部多余元素
while(!S.empty()){
CraphNode tmp35=S.top();
S.pop();
printf("当前选取节点 %d 当前选取的节点颜色 %s\n",tmp35.index,colorName[tmp35.color]);
}
}
else{
printf("该地图不存在仅用 %d 种颜色着色的方案\n",M);
}
}
int main()
{
fillColor();
return 0;
}
5.10 地图着色(递归实现)
#include<iostream>
#include<stdio.h>
#include"Stack.h"
using namespace std;
#define N 7 //地图区域数量
#define M 4//最多允许使用颜色的数量
bool maps[][N]{//注意该矩阵是对称矩阵
{0,1,1,1,1,1,0},
{1,0,0,0,0,1,0},
{1,0,0,1,1,0,0},
{1,0,1,0,1,1,0},
{1,0,1,1,0,1,0},
{1,1,0,1,1,0,0},
{0,0,0,0,0,0,0}
};
const char* colorName[6] = { " ","紫","黄","红","绿" };
int color[N+2];//存储节点颜色
int flag=0;//标志是否找到染色方案
bool anyConflict(int r)//检查是否撞色
{
for(int i=0;i<N;i++){
if(maps[r-1][i]&&color[i+1]==color[r]&&color[r]!=0){
//cout<<r<<" zjs"<<endl;
return true;
}
}
return false;//返回不冲突
}
void dfs(int n,int col){
if(flag==1) return;//已经找到
color[n]=col;
if(anyConflict(n)) return;//如果冲突
if(n>N){//找到染色方案
flag=1;
for(int i=1;i<=N;i++){
printf("当前节点 %d 选取的颜色为 %s\n",i,colorName[color[i]]);
}
return ;
}
for(int i=1;i<=M;i++){
dfs(n+1,i);//递归到下一层
color[n+1]=0;//回溯
}
}
int main()
{
dfs(0,1);
return 0;
}
5.11 进制转换
//省略Stack类模板
void convert( Stack<char> & S, __int64 n, int base ) {//数的值为n，进制为 base
char digit[] = "0123456789ABCDEF"; //数位符号，如有必要可相应扩充
while ( n > 0 ) { //由低到高，逐一计算出新进制下的各数位
S.push( digit[ n % base ] ); //余数（当前的数位）入栈
n /= base; //n更新为其对base的除商
}
} //新进制下由高到低的各数位，自顶而下保存于栈S中
int main()
{
n=10000;//表示要转换进制的数的值
base=10;//表示将要转换的进制
Stack<char> S; convert( S, n, base); //用栈记录转换得到的各数位
while ( ! S.empty() ) printf( "%c", S.pop() ); //逆序输出
return 0;
}
5.12 中序遍历
template <typename T,typename VST>
void travIn_I2(BinNodPosi(T) x,VST&visit){
Stack<BinNodPosi(T)>S;//辅助栈
while(true){
if(x){
S.push(x);
x=x->lc;
}
else if(!S.empty){
x=S.pop();
visit(x->data);
x=x->rc
}
else break;
}
}
5.13 回溯法求解过桥问题
（选做）3、用回溯法求解“深夜过独木桥问题”：有N个人深夜要过一座独木桥，他们仅有一盏灯，过桥必须有灯，独木桥最多只能两人持灯过桥，每个人行走的速度不同，问这N个人全部过桥的最短时间是多少？打印过桥步骤。
例如：假定N=4，每个人过桥所需时间分别为2分钟、3分钟、7分钟、11分钟。
提示：
（1）先借助堆栈写出过桥算法。
设这4个人为A、B、C、D，一种显而易见的过桥步骤为：
A和B过桥 --3分钟 --累计3分钟
A回来 --2分钟 --累计5分钟
A和C过桥 --7分钟 --累计12分钟
A回来 --2分钟 --累计14分钟
A和D过桥 --11分钟 --累计25分钟
这样总共是25分钟可以过桥（不是最优解）。
（2）求最优解
不管从哪一端过桥，都需要尝试所有的过桥方案并压栈，从中找出最优解，例如：
最初状态[0,0,0,0]，过桥方案可以是AB、AC、AD、BC、BD、CD共6种选择
中间状态[1,1,1,0]，返回方案可以是A、B、C共3种选择
实际上，不管怎么走总是可以所有人过桥的，最初我们可以设最优解为无穷大，得到第一种过桥方案后，将最优解设为该过桥时间；后续就是用回溯法测试所有可能性：如果得到另一过桥方案并且比最优解小，就将最优解设为该过桥时间；如果中途某种走法超过了最优解就不用再走下去，回溯到上一步测试另一种走法。
每次求出一个解后，打印出该解的过桥步骤（打印的格式可以参考上面的截图，从栈底打印至栈顶，同时算出累计时间），显然，最后一个打印出来的过桥步骤就是最优解。
#include<iostream>
#include<string.h>
#include<stack>
using namespace std;
struct bitmap{
int len=0;//状态
int sum=0;//花费
};
stack<bitmap> stk;
int vis[100];
int minn=1000;
int main()
{
int value[]={2,3,7,11};
bitmap start;
start.len=0;
start.sum=0;
stk.push(start);//初始状态压入,存入回来过后的状态图
while(!stk.empty()){
start=stk.top();
stk.pop();
for(int i=0;i<4;i++){
for(int j=i;j<4;j++){
//cout<<"capacity as "<<stk.size()<<endl;
if(i!=j&&((start.len>>i)&1)==0&&((start.len>>j)&1)==0){
start.len=start.len+(1<<i)+(1<<j);
start.sum=start.sum+max(value[i],value[j]);
if(start.len==15){//找到过桥的方法
minn=min(minn,start.sum);
//回溯
start.len=start.len-(1<<i)-(1<<j);
start.sum=start.sum-max(value[i],value[j]);
continue;
//cout<<start.sum<<endl;
}
for(int k=0;k<4;k++){
if((start.len>>k)&1){
start.len-=(1<<k);
start.sum+=value[k];
stk.push(start);
//回溯
start.len+=(1<<k);
start.sum-=value[k];
}
}
//回溯
start.len=start.len-(1<<i)-(1<<j);
start.sum=start.sum-max(value[i],value[j]);
}
}
}
}
cout<<minn<<endl;
return 0;
}
推荐阅读
-
5.stack栈基本应用
-
支付宝支付之“单笔转账到支付宝账户接口”的调用（生成签名、上传应用公钥、下载SDK、接口调用、报错自动排查、查看错误码）
-
5.栈的应用
-
堆的应用之TOP K问题
-
5. linux下的栈帧分析
-
解决spring boot应用以docker容器方式启动后，进程ID是1而导致的jstack和jmap等命令不可用的问题 博客分类： dockersprng boot docker spring-boot
-
解决spring boot应用以docker容器方式启动后，进程ID是1而导致的jstack和jmap等命令不可用的问题 博客分类： dockersprng boot docker spring-boot
-
概括数据库应用系统的性能优化 博客分类： mysql
-
如何通过不同的域名访问发布到Apache上不同的Appeon Web应用？ WebApache应用服务器PowerBuilderC#
-
关于使用LoadRunner对Appeon Web应用进行压力测试的初步介绍 LoadrunnerWeb应用服务器脚本PowerBuilder