#include "stdafx.h"
#include <stdio.h>
#include <iostream>
#include <string.h>
using namespace std;
#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define UNDERFLOW -2
#define STACK_INIT_SIZE 80
#define STACKINCREMENT 10
typedef int status;
#define ElemType char
typedef struct {
ElemType *base;
ElemType *top;
int stacksize;
}SqStack;
SqStack S;
#define MAXQSIZE 80
typedef struct {
ElemType *base;
int front;
int rear;
}SqQueue;
SqQueue Q;
status InitStack(SqStack &S) //初始化栈
{
S.base = (ElemType*)malloc(STACK_INIT_SIZE * sizeof(ElemType));
if (!S.base)exit(OVERFLOW);
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
return OK;
}
status InitQueue(SqQueue &Q) { //初始化队列
Q.base = (ElemType*)malloc(MAXQSIZE * sizeof(ElemType));
if (!Q.base)exit(OVERFLOW);
Q.front = Q.rear = 0;
return OK;
}
status Push(SqStack &S, ElemType e) {//入栈
if (S.top-S.base == S.stacksize) {
S.base = (ElemType*)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(ElemType));
if (!S.base)exit(OVERFLOW);
S.top = S.base + S.stacksize;
S.stacksize += STACKINCREMENT;
}
*S.top++ = e;
return OK;
}
status EnQueue(SqQueue &Q, ElemType e) { //入队
if ((Q.rear + 1) % MAXQSIZE == Q.front)
return ERROR;//队满
Q.base[Q.rear] = e;
Q.rear = (Q.rear + 1) % MAXQSIZE;
return OK;
}
status Pop(SqStack &S, ElemType &e) {//出栈
if (S.top == S.base)exit(UNDERFLOW);
e = *(S.top=S.top-1);
return OK;
}
status DeQueue(SqQueue &Q, ElemType &e) { //出队
if (Q.front == Q.rear)return ERROR; //队空
e = Q.base[Q.front];
Q.front = (Q.front + 1) % MAXQSIZE;
return OK;
}
status StackEmpty(SqStack S) {//是否为空栈
return S.base == S.top;
}
status QueueEmpty(SqQueue Q) {//是否为空队
return Q.rear == Q.front;
}
void algo(SqQueue &Q) {//栈实现队的首尾逆置
ElemType e;
InitStack(S);
cout << " 栈逆置队列前元素如下：";
while (!QueueEmpty(Q)) {
DeQueue(Q, e);
cout << e;
Push(S, e);
}
cout << endl;
while (!StackEmpty(S)) {
Pop(S, e);
EnQueue(Q, e);
}
}
status match(char exp[50]) {//括号是否匹配
InitStack(S);
ElemType e;
for (int i = 0; i < strlen(exp); i++) {
switch (exp[i]) {
case '(':
case '[':
Push(S, exp[i]);
break;
case ')':
if (!StackEmpty(S))
{
Pop(S, e);
if (e == '(')
break;
else
return ERROR;
}
else
return ERROR;
case ']':
if (!StackEmpty(S))
{
Pop(S, e);
if (e == '[')
break;
else
return ERROR;
}
else
return ERROR;
}
}
if (StackEmpty(S))
return OK;
return ERROR;
}
char inttochar(int n) {//整型转化为字符型
switch (n) {
case 0:
return '0';
case 1:
return '1';
case 2:
return '2';
case 3:
return '3';
case 4:
return '4';
case 5:
return '5';
case 6:
return '6';
case 7:
return '7';
case 8:
return '8';
case 9:
return '9';
case 10:
return 'A';
case 11:
return 'B';
case 12:
return 'C';
case 13:
return 'D';
case 14:
return 'E';
case 15:
return 'F';
}
}
void conversion(int data, int r) {//进制转换
ElemType e;
InitStack(S);
while (data) {
Push(S, inttochar(data%r));
data = data / r;
}
while (!StackEmpty(S)) {
Pop(S, e);
cout << e;
}
cout << endl << endl;
}
int main() {
InitQueue(Q);
ElemType e;
int num, data, r;
char str[30] = "";
char exp[50];
cout << "\t\t\t\t*\t\t\t\t\t*";
cout << endl << "\t\t\t\t*\t计科1512-02210151232-杨少通\t*" << endl;
cout << "\t\t\t\t*****************************************" << endl << endl;
cout << "****************栈逆置队列元素****************" << endl << endl;
cout << " 请输入初始化队列元素个数:";
cin >> num;
for (int k= 0; k < num; k++) {
cout << " 请输入第" << k + 1 << "个元素:";
cin >> e;
EnQueue(Q, e);
}
algo(Q);
cout << " 栈逆置队列后元素如下：";
while (!QueueEmpty(Q))
{
DeQueue(Q, e);
cout << e;
}
cout << endl << endl;
cout << "**************表达式括号是否匹配**************" << endl << endl;
cout << " 请输入表达式:";
cin >> exp;
if (match(exp))
cout << " 表达式括号匹配！" << endl << endl;
else
cout << " 表达式括号不匹配！" << endl << endl;
cout << "**************十进制转换为R进制***************" << endl << endl;
cout << " 请输入十进制数：";
cin >> data;
cout << " 请输入要转换的进制数（如：2、8、16）：";
cin >> r;
cout << " " << data << "转换为" << r << "进制数为：";
conversion(data, r);
cout << "***********判断是否为中心对称字符串***********" << endl << endl;
cout << " 请输入字符串：";
cin >> str;
for (int i = 0; i < strlen(str); i++)
Push(S, str[i]);
for (int j = 0; j < strlen(str); j++)
{
Pop(S, e);
if (str[j] != e)
{
cout << " “" << str << "”不是中心对称的字符串！" << endl << endl;
return 0;
}
}
cout << " “" << str << "”是中心对称的字符串！" << endl << endl;
return 0;
}
已有 2891 位网友参与，快来吐槽：
发表评论