实验.cpp
1 //编写程序，实现顺序栈的基本运算：初始化ok、入栈ok、出栈ok；
2 //应用顺序栈实现数制转换：把任意非负十进制正整数转换为n（n可以为2、8、16等等）进制数输出ok，给出至少5组测试数据及结果。；
3 //应用顺序栈，编程实现表达式（只包含 + 、 - 、 * 、 / 四种运算符及左右圆括号，操作数为整数）的计算；至少给出3组测试数据及结果。
4 //编写程序，实现循环队列的基本运算：初始化、入队、出队。
5
6
7 #include<iostream>
8 #include<cstdio>
9 using namespace std;
10
11 #define MAX 100
12
13 //定义数据类型
14 typedef int DataType;
15 //栈的定义
16 typedef struct
17 {
18 DataType data[MAX]; //顺序栈的存储类型
19 int top; //记录栈顶的指针，在顺序栈中类似于数组下标
20 }Seqstack;
21
22 //栈的初始化
23 void InitStack(Seqstack* s)
24 {
25 s->top = -1; //初始化栈顶指针为-1
26 }
27
28 //判断栈是否为空
29 int EmptyStack(Seqstack* s)
30 {
31 if (s->top == -1)
32 return 1; //若空返回1，非空返回0
33 else
34 return 0;
35 }
36
37 //判断栈是否已满
38 int FullStack(Seqstack* s)
39 {
40 if (s->top == MAX - 1)
41 return 1; //若满返回1，非空返回0
42 else
43 return 0;
44 }
45
46 //入栈
47 int Push(Seqstack* s, DataType x)
48 {
49 if (FullStack(s)) //调用函数判断栈是否已满
50 {
51 printf("栈满，不可入栈!");
52 return 0;
53 }
54 else
55 {
56 s->top++; //将栈顶指针上一位
57 s->data[s->top] = x;
58 return 1;
59 }
60 }
61
62 //出栈
63 int Pop(Seqstack* s, DataType* x)
64 {
65 if (EmptyStack(s))
66 {
67 return 0;
68 }
69 else
70 {
71 *x = s->data[s->top];
72 s->top--;
73 return 1;
74 }
75 }
76
77 //出栈并输出栈中元素
78 void printStack(Seqstack* s)
79 {
80 DataType e;
81 //cout << "栈中元素有：";
82 while (Pop(s, &e))
83 printf("%d ", e);
84 cout << endl;
85 }
86
87 void OutputStack(Seqstack* S)
88 {
89 cout << "栈中元素有：";
90 for (int i = S->top; i >= 0; i--)
91 cout << S->data[i];
92 cout << endl;
93 }
94
95 void ChangeStack(DataType e, int con) {
96 string s;
97 // 处理 e 为 0 的情况
98 if (e == 0) {
99 s.push_back('0');
100 }
101 // 十进制转换为目标进制
102 while (e) {
103 char digit = (e % con) + '0';
104 if (digit > '9') {
105 digit = digit - '0' + 'A'; // 转换为 A, B, C 等十六进制字符
106 }
107 s.push_back(digit);
108 e /= con;
109 }
110 // 反转字符串
111 reverse(s.begin(), s.end());
112 cout << s << endl;
113 }
114
115 void ConvertStack(Seqstack* S, int con) {
116 for (int i = 0; i <= S->top; i++) {
117 DataType e = S->data[i];
118 ChangeStack(e, con);
119 }
120 }
121
122 void Menu()
123 {
124 puts("****************");
125 puts("1.初始化");
126 puts("2.判断栈为空");
127 puts("3.入栈");
128 puts("4.出栈");
129 puts("5.取栈顶元素");
130 puts("6.把栈中元素转换进制");
131 puts("0.程序结束");
132 puts("****************");
133 }
134
135 int main()
136 {
137 Seqstack S;
138 int choice = -1,num,n;
139 DataType e;
140 Menu();
141 while (choice == -1)
142 {
143 cout << "你的选择是：";
144 cin >> num;
145 cout << endl;
146 switch (num)
147 {
148 case 1:
149 InitStack(&S);
150 cout << "初始化完成！\n";
151 break;
152 case 2:
153 if (EmptyStack(&S))
154 cout << "栈为空！\n";
155 else
156 cout << "栈不为空！\n";
157 break;
158 case 3:
159 cout << "请输入入栈的数量：";
160 cin >> n;
161 cout << endl;
162 cout << "输入入栈的元素：";
163 for (int i = 0; i < n; i++)
164 {
165 scanf("%d", &e);
166 Push(&S, e);
167 }
168 break;
169 case 4:
170 cout << "输出栈中元素：";
171 //Pop(&S, &e);
172 printStack(&S);
173 //cout << endl;
174 break;
175 case 5:
176 cout << "栈顶元素为：";
177 if (Pop(&S, &e))
178 cout << e;
179 else
180 cout << "栈为空！";
181 cout << endl;
182 break;
183 case 6:
184 cout << "输入转换的进制：";
185 int con;
186 cin >> con;
187 ConvertStack(&S, con);
188 break;
189 case 0:
190 choice = 0;
191 break;
192 default:printf("选择有误请重新输入！\n");
193 }
194 }
195 return 0;
196 }
实验.cpp
二则运算.cpp
1 #include <iostream>
2 #include <stack>
3 #include <string>
4 #include <cctype> // for isdigit function
5
6 using namespace std;
7
8 // 运算符优先级函数
9 int getPriority(char op) {
10 if (op == '+' || op == '-') return 1;
11 if (op == '*' || op == '/') return 2;
12 return 0;
13 }
14
15 // 执行简单的二元运算
16 int applyOperator(int left, int right, char op) {
17 switch (op) {
18 case '+': return left + right;
19 case '-': return left - right;
20 case '*': return left * right;
21 case '/': return left / right;
22 default: return 0;
23 }
24 }
25
26 // 计算表达式
27 int calculateExpression(const string& expr) {
28 stack<int> values; // 存储操作数
29 stack<char> ops; // 存储运算符
30
31 int n = expr.size();
32 for (int i = 0; i < n; ++i) {
33 // 跳过空格
34 if (isspace(expr[i])) continue;
35
36 // 如果是数字，处理多位数
37 if (isdigit(expr[i])) {
38 int val = 0;
39 while (i < n && isdigit(expr[i])) {
40 val = val * 10 + (expr[i] - '0');
41 ++i;
42 }
43 --i; // 由于循环后 i 会多加 1，需要回退
44 values.push(val);
45 }
46 // 如果是左括号，压入运算符栈
47 else if (expr[i] == '(') {
48 ops.push(expr[i]);
49 }
50 // 如果是右括号，计算直到遇到左括号
51 else if (expr[i] == ')') {
52 while (!ops.empty() && ops.top() != '(') {
53 int right = values.top(); values.pop();
54 int left = values.top(); values.pop();
55 char op = ops.top(); ops.pop();
56 values.push(applyOperator(left, right, op));
57 }
58 ops.pop(); // 弹出 '('
59 }
60 // 如果是运算符
61 else if (expr[i] == '+' || expr[i] == '-' || expr[i] == '*' || expr[i] == '/') {
62 while (!ops.empty() && getPriority(ops.top()) >= getPriority(expr[i])) {
63 int right = values.top(); values.pop();
64 int left = values.top(); values.pop();
65 char op = ops.top(); ops.pop();
66 values.push(applyOperator(left, right, op));
67 }
68 ops.push(expr[i]);
69 }
70 }
71
72 // 处理栈中剩余的运算符
73 while (!ops.empty()) {
74 int right = values.top(); values.pop();
75 int left = values.top(); values.pop();
76 char op = ops.top(); ops.pop();
77 values.push(applyOperator(left, right, op));
78 }
79
80 return values.top(); // 栈顶就是最终结果
81 }
82
83 int main() {
84 // 测试用例
85 string expr1 = "3 + 2 * 2"; // 7
86 string expr2 = "(1 + 2) * 3 + 4"; // 11
87 string expr3 = "3 + 5 / 2"; // 5
88
89 cout << "Expression: " << expr1 << " = " << calculateExpression(expr1) << endl;
90 cout << "Expression: " << expr2 << " = " << calculateExpression(expr2) << endl;
91 cout << "Expression: " << expr3 << " = " << calculateExpression(expr3) << endl;
92
93 return 0;
94 }
95 #include <iostream>
96 #include <stack>
97 #include <string>
98 #include <cctype> // for isdigit function
99
100 using namespace std;
101
102 // 运算符优先级函数
103 int getPriority(char op) {
104 if (op == '+' || op == '-') return 1;
105 if (op == '*' || op == '/') return 2;
106 return 0;
107 }
108
109 // 执行简单的二元运算
110 int applyOperator(int left, int right, char op) {
111 switch (op) {
112 case '+': return left + right;
113 case '-': return left - right;
114 case '*': return left * right;
115 case '/': return left / right;
116 default: return 0;
117 }
118 }
119
120 // 计算表达式
121 int calculateExpression(const string& expr) {
122 stack<int> values; // 存储操作数
123 stack<char> ops; // 存储运算符
124
125 int n = expr.size();
126 for (int i = 0; i < n; ++i) {
127 // 跳过空格
128 if (isspace(expr[i])) continue;
129
130 // 如果是数字，处理多位数
131 if (isdigit(expr[i])) {
132 int val = 0;
133 while (i < n && isdigit(expr[i])) {
134 val = val * 10 + (expr[i] - '0');
135 ++i;
136 }
137 --i; // 由于循环后 i 会多加 1，需要回退
138 values.push(val);
139 }
140 // 如果是左括号，压入运算符栈
141 else if (expr[i] == '(') {
142 ops.push(expr[i]);
143 }
144 // 如果是右括号，计算直到遇到左括号
145 else if (expr[i] == ')') {
146 while (!ops.empty() && ops.top() != '(') {
147 int right = values.top(); values.pop();
148 int left = values.top(); values.pop();
149 char op = ops.top(); ops.pop();
150 values.push(applyOperator(left, right, op));
151 }
152 ops.pop(); // 弹出 '('
153 }
154 // 如果是运算符
155 else if (expr[i] == '+' || expr[i] == '-' || expr[i] == '*' || expr[i] == '/') {
156 while (!ops.empty() && getPriority(ops.top()) >= getPriority(expr[i])) {
157 int right = values.top(); values.pop();
158 int left = values.top(); values.pop();
159 char op = ops.top(); ops.pop();
160 values.push(applyOperator(left, right, op));
161 }
162 ops.push(expr[i]);
163 }
164 }
165
166 // 处理栈中剩余的运算符
167 while (!ops.empty()) {
168 int right = values.top(); values.pop();
169 int left = values.top(); values.pop();
170 char op = ops.top(); ops.pop();
171 values.push(applyOperator(left, right, op));
172 }
173
174 return values.top(); // 栈顶就是最终结果
175 }
176
177 int main() {
178 // 测试用例
179 string expr1 = "3 + 2 * 2"; // 7
180 string expr2 = "(1 + 2) * 3 + 4"; // 11
181 string expr3 = "3 + 5 / 2"; // 5
182
183 cout << "Expression: " << expr1 << " = " << calculateExpression(expr1) << endl;
184 cout << "Expression: " << expr2 << " = " << calculateExpression(expr2) << endl;
185 cout << "Expression: " << expr3 << " = " << calculateExpression(expr3) << endl;
186
187 return 0;
188 }
二则运算.cpp
队列.cpp
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #include<stdbool.h>
5 #include<assert.h>
6
7 typedef int QDateType;
8 typedef struct QueueNode
9 {
10 struct QueueNode* next;
11 QDateType date;
12 }QNode;
13 typedef struct Queue
14 {
15 QNode* head;
16 QNode* tail;
17 }Queue;
18
19 #define _CRT_SECURE_NO_WARNINGS 1
20 //队列的初始化
21 void QueueInit(Queue* pq)
22 {
23 assert(pq);
24 pq->head = NULL;
25 pq->tail = NULL;
26 }
27 //队列的销毁
28 void QueueDestory(Queue* pq)
29 {
30 assert(pq);
31
32 QNode* cur = pq->head;
33 while (cur)
34 {
35 QNode* next = cur->next;
36 free(cur);
37 cur = next;
38 }
39 pq->head = pq->tail = NULL;
40 }
41 //队列的插入
42 void QueuePush(Queue* pq, QDateType x)
43 {
44 assert(pq);
45 QNode* newnode = (QNode*)malloc(sizeof(QNode));
46 if (newnode == NULL)
47 {
48 printf("malloc is fail\n");
49 exit(-1);
50 }
51 //对新节点进行初始化
52 newnode->date = x;
53 newnode->next = NULL;
54
55 //对新结点进行连接
56 if (pq->head == NULL)
57 {
58 //头结点是空的，也就是第一个数据的插入
59 pq->head = pq->tail = newnode;
60 }
61 else
62 {
63 //非第一个数据的插入
64 pq->tail->next = newnode;
65 pq->tail = newnode;
66 }
67 }
68 //队列的删除
69 void QueuePop(Queue* pq)
70 {
71 assert(pq);
72 //确保队列不是空的队列
73 assert(pq->head);
74 //如果只有一个结点，防止tail形成野指针
75 if (pq->head->next == NULL)
76 {
77 free(pq->head);
78 pq->head = pq->tail = NULL;
79 }
80 //不是只有一个结点
81 else
82 {
83 //保存第二个队列结点
84 QNode* next = pq->head->next;
85 free(pq->head);
86 pq->head = next;
87 }
88 }
89 //判断队列是否为空
90 bool QueueEmpty(Queue* pq)
91 {
92 assert(pq);
93 return pq->head == NULL;
94 }
95 //取出队头的数据
96 QDateType QueueFront(Queue* pq)
97 {
98 assert(pq);
99 assert(pq->head);
100 return pq->head->date;
101 }
102 //取出队尾的数据
103 QDateType QueueBack(Queue* pq)
104 {
105 assert(pq);
106 assert(pq->head);
107 return pq->tail->date;
108 }
109 //取出数据的个数
110 int QueueSize(Queue* pq)
111 {
112 assert(pq);
113 int size = 0;
114 QNode* cur = pq->head;
115 while (cur)
116 {
117 cur = cur->next;
118 size++;
119 }
120 return size;
121 }
122
123 void TestQueue()
124 {
125 Queue q;
126 QueueInit(&q);
127 QueuePush(&q, 1);
128 QueuePush(&q, 2);
129 QueuePush(&q, 3);
130 QueuePush(&q, 4);
131 QueuePush(&q, 5);
132
133 while (!QueueEmpty(&q))
134 {
135 printf("%d ", QueueFront(&q));
136 QueuePop(&q);
137 }
138 printf("\n");
139 QueueDestory(&q);
140 }
141 int main()
142 {
143 TestQueue();
144 return 0;
145 }
队列.cpp
标签：pq,return,int,expr,top,实验,values,数据结构 From： https://www.cnblogs.com/DREAMSRING/p/18529516