南京网站官网建设,wordpress会员下载,合肥做网站的公司,深圳网站建设找哪家公司好目录 1. 中缀表达式转换为后缀表达式 2. 括号匹配问题
3. 栈实现队列
4. 约瑟夫环 1. 中缀表达式转换为后缀表达式
【问题描述】 输入一个中缀表达式#xff0c;表达式中有、-、*、/四种运算以及#xff08;、#xff09;#xff0c;表达式中的其他符号为大写的字母。实…目录 1. 中缀表达式转换为后缀表达式 2. 括号匹配问题
3. 栈实现队列
4. 约瑟夫环 1. 中缀表达式转换为后缀表达式
【问题描述】 输入一个中缀表达式表达式中有、-、*、/四种运算以及、表达式中的其他符号为大写的字母。实现一个算法得到相应的后缀表达式。
【输入形式】 一个式子的中缀表达式以#结束
【输出形式】 相应的后缀表达式
【样例输入】 A*(B-C)/DE#
【样例输出】 ABC-*D/E
【评分标准】 请大家在程序中写出必要的注释如果程序没有必要的注释将酌情扣分 #includestdio.h
#includestring.h#define MAX_SIZE 100
typedef struct {char data[MAX_SIZE];int top;
}Stack;void init(Stack *stack){stack-top-1;
}int isEmpty(Stack *stack){return stack-top-1;
}int isFull(Stack *stack){return stack-topMAX_SIZE-1;
}void push(Stack *stack,char c){if(isFull(stack)){printf(Stack overflow\n);return;}stack-data[stack-top]c;
}char pop(Stack *stack){if(isEmpty(stack)){printf(Stack underflow\n);return \0;}return stack-data[stack-top--];
}int getPriority(char c){if(c||c-){return 1;}else if(c*||c/){return 2;}else{return 0;}
}void infixToPostfix(char *infix, char *postfix){Stack s;init(s);int i0, j0;while(infix[i]!#){if(infix[i]Ainfix[i]Z){postfix[j]infix[i];}else if(infix[i](){push(s, infix[i]);}else if(infix[i])){while(!isEmpty(s) s.data[s.top]!(){postfix[j]pop(s);}if(!isEmpty(s) s.data[s.top](){pop(s);}}else{while(!isEmpty(s) getPriority(infix[i])getPriority(s.data[s.top])){postfix[j]pop(s);}push(s, infix[i]);}i;}while(!isEmpty(s)){postfix[j]pop(s);}postfix[j]\0;
}int main(){char infix[MAX_SIZE];scanf(%s, infix);char postfix[MAX_SIZE];infixToPostfix(infix, postfix);printf(%s\n, postfix);return 0;
} 2. 括号匹配问题
【问题描述】
假设一算术表达式中包括三种括号圆括号和方括号[和]花括号{和}且三种括号可按意 次序嵌套使用试编写程序判定输入的表达式所含的括号是否正确配对出现已知表达式已存入数据元素为字符的顺序表中。若匹配则返回1否则返回0。 【输入形式】
含括号的算数表达式 【输出形式】
1或者0
【样例输入】
3(44*[5-{6*[7*45-10]}])
【样例输出】
1
【样例说明】
判断括号是否匹配涉及两方面括号个数和出现次序的判定。 【评分标准】
#include stdio.h
#include string.h#define MAX_SIZE 100typedef struct {char data[MAX_SIZE];int top;
} Stack;void init(Stack *stack) {stack-top -1;
}int isEmpty(Stack *stack) {return stack-top -1;
}int isFull(Stack *stack) {return stack-top MAX_SIZE - 1;
}void push(Stack *stack, char c) {if (isFull(stack)) {printf(Stack overflow\n);return;}stack-data[stack-top] c;
}char pop(Stack *stack) {if (isEmpty(stack)) {printf(Stack underflow\n);return \0;}return stack-data[stack-top--];
}int isMatching(char left, char right) {if (left ( right )) {return 1;} else if (left [ right ]) {return 1;} else if (left { right }) {return 1;} else {return 0;}
}int isParenthesesMatching(char *expression) {Stack stack;init(stack);int i;int length strlen(expression);for ( i 0; i length; i) {char c expression[i];if (c ( || c [ || c {) {push(stack, c);} else if (c ) || c ] || c }) {if (isEmpty(stack)) {return 0;}char top pop(stack);if (!isMatching(top, c)) {return 0;}}}return isEmpty(stack);
}int main() {char expression[MAX_SIZE];fgets(expression, MAX_SIZE, stdin);int result isParenthesesMatching(expression);printf(%d\n, result);return 0;
}
3. 栈实现队列
【问题描述】
请使用栈类实现队列的类。
【输入形式】
第一行一个整数n
接下来n行每行一个整数依次表示已经在队列中的数。
接下来一行一个整数m。
接下来m行有两种情况1. 一个整数请将其入列。2. 字符串D表示出列操作。
【输出形式】
若干行每行一个出列的输出。
【样例输入】
3
1
2
3
2
4
D
【样例输出】
1
【样例说明】
队列中原来有123三个数第一个操作使4入列第二个操作出列弹出队头的1 【评分标准】
通过所有数据
#include stdio.h
#include string.h#define MAX_SIZE 100typedef struct {int data[MAX_SIZE];int top;
} Stack;void init(Stack *stack) {stack-top -1;
}int isEmpty(Stack *stack) {return stack-top -1;
}int isFull(Stack *stack) {return stack-top MAX_SIZE - 1;
}void push(Stack *stack, int num) {if (isFull(stack)) {printf(Stack overflow\n);return;}stack-data[stack-top] num;
}int pop(Stack *stack) {if (isEmpty(stack)) {printf(Stack underflow\n);return 0;}return stack-data[stack-top--];
}int main() {int n, m;scanf(%d, n);Stack s1, s2;init(s1);init(s2);int i;for (i 0; i n; i) {int num;scanf(%d, num);push(s1, num);}scanf(%d, m);for (i 0; i m; i) {char temp_str[2];scanf(%s, temp_str);if (strcmp(temp_str, D) 0) {if (isEmpty(s2)) {while (!isEmpty(s1)) {int num pop(s1);push(s2, num);}}int result pop(s2);printf(%d\n, result);n--;} else {int num atoi(temp_str);push(s1, num);n;}}return 0;
} 4. 约瑟夫环 【问题描述】
n个人围成一个圈按顺时针方向一次编号1、2、3、……、n从第一个人开始顺时针方向依次报数1、2、3、……报数m的人被淘汰然后下一个人再从1开始报数一直重复该过程。由于人数是有限的因此最后一定只会剩下一个人求这个人的编号。
【输入形式】
第一行一个整数n表示约瑟夫环的总人数。
第二行一个整数m表示报到m的人被淘汰。
【输出形式】 一行一个整数约瑟夫环最终剩下的人的编号。
【样例输入】
5
2
【样例输出】
3
【样例说明】
5个人围成一圈编号12345
第一轮2号淘汰剩下1345
第二轮从3开始报数4号淘汰剩下135
第三轮从5开始报数1号淘汰剩下35
第四轮从3开始报数5号淘汰剩下3。 【评分标准】
通过所有数据
#include stdio.h
#include stdlib.htypedef struct Node {int data;struct Node* next;
} Node,*LinkList;LinkList createNode(int data) {LinkList newNode (LinkList)malloc(sizeof(Node));newNode-data data;newNode-next NULL;return newNode;
}void appendNode(LinkList* head, int data) {LinkList newNode createNode(data);if (*head NULL) {*head newNode;newNode-next *head;} else {LinkList temp *head;while (temp-next ! *head) {temp temp-next;}temp-next newNode;newNode-next *head;}
}void deleteNode(LinkList* head, int m) {if (*head NULL) {return;}LinkList current *head;LinkList prev NULL;while (current-next ! *head) {prev current;current current-next;}if (current *head current-next *head) {*head NULL;free(current);return;}int i;for ( i 1; i m; i) {prev current;current current-next;}prev-next current-next;free(current);*head prev-next;
}int josephus(int n, int m) {LinkList head NULL;int i;for (i 1; i n; i) {appendNode(head, i);}while ( head!head-next) {deleteNode(head, m);}return head-data;
}int main() {int n, m;scanf(%d%d, n, m);int result josephus(n, m);printf(%d\n, result);return 0;
}
