仅供课外学习使用，任何个人与机构不得利用此文章进行任何形式的作弊。
01基于栈的中缀算术表达式求值
#include <iostream>
#include<iomanip>
#define MAXSIZE 100
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
using namespace std;
typedef struct
{//运算符栈char *base;char *top;int stacksize;
}SqStack1;
Status InitStack1(SqStack1 &S)
{//运算符栈初始化S.base = new char[MAXSIZE];if(!S.base) exit(OVERFLOW);S.top = S.base;S.stacksize = MAXSIZE;return OK;
}
Status Push1(SqStack1 &S, char e)
{//运算符栈入栈if(S.top - S.base == S.stacksize) return ERROR;*S.top++ = e;return OK;
}
Status Pop1(SqStack1 &S)
{//运算符栈出栈if(S.top == S.base) return ERROR;--S.top;return OK;
}
char GetTop1(SqStack1 S)
{//运算符栈取栈顶元素if(S.top != S.base)return *(S.top - 1);return ERROR;
}
typedef struct
{//操作数栈double *base;double *top;int stacksize;
}SqStack2;
Status InitStack2(SqStack2 &S)
{//操作数栈初始化S.base = new double[MAXSIZE];if(!S.base) exit(OVERFLOW);S.top = S.base;S.stacksize = MAXSIZE;return OK;
}
Status Push2(SqStack2 &S,double e)
{//操作数栈入栈if(S.top - S.base == S.stacksize) return ERROR;*S.top++ = e;return OK;
}
Status Pop2(SqStack2 &S)
{//操作数栈出栈if(S.top == S.base) return ERROR;--S.top;return OK;
}
double GetTop2(SqStack2 S)
{//操作数栈取栈顶元素if(S.top != S.base)return *(S.top - 1);return ERROR;
}
double Calculate(double a,char op,double b)
{//计算表达式“a op b”的值switch (op) {case '+':return a + b;break;case '-':return a - b;break;case '*':return a * b;break;case '/':if(b == 0) return ERROR;return a / b;break; default:return ERROR;break;}
}char Precede(char a,char b)
{//比较运算符a和b的优先级switch (a) {case '+':case '-':switch (b) {case '+':case '-':case ')':case '=':return '>';break;case '*':case '/':case '(':return '<';break;}break;case '*':case '/':switch (b) {case '+':case '-':case '*':case '/':case ')':case '=':return '>';break;case '(':return '<';break;}break; case '(':switch (b) {case '+':case '-':case '*':case '/':case '(':return '<';break;case ')':return '=';break;}break;case ')':switch (b) {case '+':case '-':case '*':case '/':case ')':case '=':return '>';break;}break; case '=':switch (b) {case '+':case '-':case '*':case '/':case '(':return '<';break;case '=':return '=';break;}break;}return ERROR;
}double EvaluateExpression(SqStack1 OPTR,SqStack2 OPND,char s[])
{//算术表达式求值的算符优先算法//设OPTR和OPND分别为运算符栈和操作数栈//表达式求值算法调用Precede函数和Calculate函数 char c, o; double a, b;for(int i = 0; s[i] != '\0'; ){c = s[i];if(!isdigit(c)){switch (Precede(GetTop1(OPTR), c)) {case '<':Push1(OPTR, c);i++;break;case '>':o = GetTop1(OPTR);Pop1(OPTR);b = GetTop2(OPND);Pop2(OPND);a = GetTop2(OPND);Pop2(OPND);Push2(OPND, Calculate(a, o, b));break;case '=':Pop1(OPTR);i++;break;default:return ERROR;break;}}else{int j = 0;char num[5] = {'\0'};do{num[j] = c;j++; i++;c = s[i];}while(isdigit(c) || c == '.');num[j] = 0;double t = atof(num);Push2(OPND, t);}}double n = GetTop2(OPND);return n;
}int main()
{//设OPTR和OPND分别为运算符栈和操作数栈SqStack1 OPTR;InitStack1(OPTR); //初始化OPND栈SqStack2 OPND;InitStack2(OPND); //初始化OPTR栈Push1(OPTR,'='); //提前在OPTR栈中放入'='，便于以后比较符号优先级 char s[100];while(cin>>s){//循环读入多组数据 if(s[0]=='=') break; //当表达式只有一个“=”时，输入结束 //输出中缀算术表达式的值cout<<fixed<<setprecision(2)<<EvaluateExpression(OPTR,OPND,s)<<endl; }return 0;
}
02中缀表达式转化为后缀表达式
#include<iostream>
using namespace std;
#define MAXSIZE 100
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
typedef struct
{char *base;char *top;int stacksize;
}SqStack;
Status InitStack(SqStack &S)
{//初始化栈S.base = new char[MAXSIZE];if(!S.base) exit(OVERFLOW);S.top = S.base;S.stacksize = MAXSIZE;return OK;
}
Status Push(SqStack &S, char e)
{//入栈if(S.top - S.base == S.stacksize) return ERROR;*S.top++ = e;return OK;
}
Status Pop(SqStack &S)
{//出栈if(S.top == S.base) return ERROR;--S.top;return OK;
}
char GetTop(SqStack S)
{//取栈顶元素if(S.top != S.base)return *(S.top - 1);else return ERROR;
}
char Precede(char a,char b)
{//比较运算符a和b的优先级switch (a) {case '+':case '-':switch (b) {case '+':case '-':case ')':case '=':return '>';break;case '*':case '/':case '(':return '<';break;}break;case '*':case '/':switch (b) {case '+':case '-':case '*':case '/':case ')':case '=':return '>';break;case '(':return '<';break;}break; case '(':switch (b) {case '+':case '-':case '*':case '/':case '(':return '<';break;case ')':return '=';break;}break;case ')':switch (b) {case '+':case '-':case '*':case '/':case ')':case '=':return '>';break;}break; case '=':switch (b) {case '+':case '-':case '*':case '/':case '(':return '<';break;case '=':return '=';break;}break;}return ERROR;
}
void InfixToSuffix(SqStack OPTR,char s[])
{//将中缀表达式转化为后缀表达式并输出 char t;for(int i = 0; s[i] != '\0'; ){while(isdigit(s[i])){cout << s[i];i++;}switch (Precede(GetTop(OPTR), s[i])) {case '<':Push(OPTR, s[i]);i++;break;case '>':t = GetTop(OPTR);Pop(OPTR);cout << t; break;case '=':t = GetTop(OPTR);Pop(OPTR);i++;break;}} cout << endl;
}int main()
{SqStack OPTR;InitStack(OPTR); //初始化操作符栈OPTRPush(OPTR,'='); //先在栈底放入'='便于以后比较符号优先级 char s[100];while(cin>>s){if(s[0]=='=')break; //当表达式只有一个“=”时，输入结束 elseInfixToSuffix(OPTR,s); //将中缀表达式转化为后缀表达式并输出 }return 0;
}
03基于栈的后缀算术表达
#include <iostream>
#include<iomanip>
#include <string>
#define MAXSIZE 100
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
using namespace std;
typedef struct
{//操作数栈double* base;double* top;int stacksize;
}SqStack;
Status InitStack(SqStack& S)
{//操作数栈初始化S.base = new double[MAXSIZE];S.top = S.base;S.stacksize = MAXSIZE;return OK;
}
Status Push(SqStack& S, double e)
{//操作数栈入栈if(S.top - S.base == S.stacksize)return ERROR;*S.top++ = e;return OK;
}
Status Pop(SqStack& S)
{//操作数栈出栈if(S.top == S.base)return ERROR;S.top--;return OK;
}
double GetTop(SqStack S)
{//操作数栈取栈顶元素if(S.top == S.base)return ERROR; //若不存在栈顶元素则返回ERRORdouble e = *(S.top - 1);return e;
}
double Calculate(double a, char op, double b)
{//计算表达式“a op b”的值switch (op) {case '+':return a + b;break;case '-':return a - b;break;case '*':return a * b;case '/':return a / b;default:return ERROR;break;}
}
double EvaluateExpression(SqStack OPND,char s[])
{//后缀算术表达式求值//设OPND为操作数栈//表达式求值算法调用Calculate函数 for(int i = 0; s[i] != '\0'; i++){if(isdigit(s[i])){
// char c = s[i];
// int j = 0;
// char num[5] = {'\0'};
// do
// {
// num[j] = c;
// j++; i++;
// c = s[i];
// }while(isdigit(c) || c == '.');
// num[j] = 0;
// double t = atof(num);
// Push(OPND, t);Push(OPND, s[i] - '0');}else if(s[i] == ' ') continue;else{if(s[i] == '=') break;double a, b;b = GetTop(OPND); Pop(OPND);a = GetTop(OPND); Pop(OPND);Push(OPND, Calculate(a, s[i], b));}}double n = GetTop(OPND);return n;
}int main()
{char s[100];//用字符数组存储表达式，每个数组元素仅存一个字符while(1){cin.getline(s,100); //输入一行含空格的后缀表达式if(s[0]=='=') break; //当表达式只有一个"="时，输入结束SqStack OPND;InitStack(OPND); //初始化数字栈cout<<fixed<<setprecision(2)<<EvaluateExpression(OPND,s)<<fixed<<setprecision(2)<<endl;}return 0;
}
04入栈和出栈的基本操作式求值
#include<iostream>
using namespace std;
#define MAXSIZE 100
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
typedef struct
{int* base;int* top;int stacksize;
}SqStack;
Status InitSqStack(SqStack& S)
{//栈的初始化S.base = new int[MAXSIZE];if(!S.base) exit(OVERFLOW);S.top = S.base;S.stacksize = MAXSIZE;return OK;
}
Status Push(SqStack& S, int e)
{//入栈if(S.top - S.base == S.stacksize)return ERROR;*S.top++ = e;return OK;
}
Status Pop(SqStack& S)
{//出栈if(S.top == S.base) return ERROR;int e;e = *--S.top;return OK;
}
Status GetTop(SqStack S)
{//取栈顶元素if(S.top != S.base)return *(S.top - 1);return ERROR;
}
void InOutS(SqStack& S, int a[], int n)
{//入栈和出栈的基本操作for(int i = 0; i < n; i++){if(a[i] == -1){int t = GetTop(S);if(S.top == S.base){cout << "POP ERROR" << endl;break;}else{cout << t << endl;Pop(S);}}else{Push(S, a[i]);}}
}int main()
{int n;while(cin>>n){if(n==0) break;SqStack S;InitSqStack(S);int a[n];for(int i=0;i<n;i++) cin>>a[i]; //整数序列InOutS(S,a,n);}return 0;
}
05双栈的基本操作
#include<iostream>
using namespace std;
typedef int Status;
typedef struct
{int top[2], bot[2];//栈顶和栈底指针int* V;//栈数组int m;//栈最大可容纳元素个数
}DblStack;
void InitDblStack(DblStack& S, int m)
{//初始化一个大小为m的双向栈S.V = new int[m];S.bot[0] = S.top[0] = -1;S.bot[1] = S.top[1] = m;
}
Status IsEmpty(DblStack S, int i)
{//判断指定的i号栈是否为空，空返回1，否则返回0if(S.top[i] == S.bot[i]) return 1;elsereturn 0;
}
Status IsFull(DblStack S)
{//判断栈是否满，满则返回1，否则返回0if(S.top[0] + 1 == S.top[1])return 1;elsereturn 0;
}
void Push(DblStack& S, int i)
{//向指定的i号栈中插入元素x，先移动指针再入栈if(IsFull(S)) exit(-1);if(i == 0)cin >> S.V[++S.top[i]];else cin >> S.V[--S.top[i]];
}void Pop(DblStack& S, int i)
{//删除指定的i号栈的栈顶元素，先出栈再移动指针if(IsEmpty(S, i))exit(-1);if(i == 0)cout << S.V[S.top[i]--] << " ";elsecout << S.V[S.top[i]++] << " ";
}int main()
{DblStack S;int m,e0,e1,d0,d1;while(cin>>m){if(m==0) break;InitDblStack(S,m);cin>>e0>>e1>>d0>>d1;while(e0--)Push(S,0);while(e1--)Push(S,1);cout<<IsFull(S)<<endl;while(d0--)Pop(S,0);cout<<!IsEmpty(S,0)<<endl;while(d1--)Pop(S,1);cout<<!IsEmpty(S,1)<<endl;}return 0;
}
06基于栈的回文字符序列判断
#include <iostream>
#define MAXSIZE 100
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
using namespace std;
typedef struct
{char* base;char* top;int stacksize;
}SqStack;
Status InitStack(SqStack& S)
{//栈初始化S.base = new char[MAXSIZE];if(!S.base) exit(OVERFLOW);S.top = S.base;S.stacksize = MAXSIZE;return OK;
}
Status Push(SqStack& S, char e)
{//入栈if(S.top - S.base == S.stacksize)return ERROR;*S.top++ = e;return OK;
}
Status Pop(SqStack& S)
{//出栈返回栈顶元素if(S.top == S.base)return ERROR;char e = *--S.top;return e;
}
Status IsPalindrome(SqStack& S, char* t)
{//判断栈的回文字符序列，不等则返回零, 相等则返回1char *p = new char[sizeof(t)];for(int i = 0; t[i]!= '\0'; i++)Push(S, t[i]);for(int i = 0; t[i]!= '\0'; i++)p[i] = Pop(S);bool flag = true;for(int i = 0; t[i]!= '\0'; i++){if(p[i] != t[i]){flag = false;break;}}p[sizeof(t)] = '\0';delete p;if(flag) return 1;else return 0;
}int main()
{char t[100];while(cin>>t&&t[0]!='0'){SqStack S;InitStack(S);if(IsPalindrome(S,t)==1) cout<<"YES"<<endl;else cout<<"NO"<<endl;}return 0;
}
07基于栈的可操作判断
#include <iostream>
#include <cstring>
#define MAXSIZE 100
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
using namespace std;
typedef struct
{char* base;char* top;int stacksize;
}SqStack;
Status InitStack(SqStack& S)
{//初始化栈S.base = new char[MAXSIZE];if(!S.base) exit(OVERFLOW);S.top = S.base;S.stacksize = MAXSIZE;return OK;
}
Status Push(SqStack& S)
{//入栈if(S.top - S.base == S.stacksize)return ERROR;S.top++;return OK;
}
Status Pop(SqStack& S)
{//出栈if(S.top == S.base) return ERROR;S.top--;return OK;
}
Status IsEmpty(SqStack S)
{//判断栈是否为空，空返回1，否则返回0if(S.top == S.base) return 1;return 0;
}
bool Judge(char a[], SqStack& S)
{//栈的可操作判断for(int i = 0; a[i] != '\0'; i++){if(a[i] == 'I'){if(!Push(S)) return false;}if(a[i] == 'O'){if(!Pop(S))return false;}}if(S.top != S.base)return false;return true;
}int main()
{char a[100];while(cin>>a){if(a[0]=='0') break;SqStack op;InitStack(op);if(Judge(a,op)) cout<<"TRUE"<<endl;else cout<<"FALSE"<<endl;}return 0;
}
