用c语言手写栈实现一个计算器
时间: 2023-05-27 22:05:01 浏览: 70
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100 // 定义栈的最大容量
typedef struct {
int top; // 栈顶指针
int* data; // 栈内数据存储数组
} Stack;
// 初始化栈
void initStack(Stack* s) {
s->data = (int*)malloc(MAX_SIZE * sizeof(int)); // 动态分配内存
s->top = -1; // 初始化栈顶指针
}
// 判断栈是否为空
int isEmpty(Stack* s) {
return s->top == -1;
}
// 判断栈是否已满
int isFull(Stack* s) {
return s->top == MAX_SIZE - 1;
}
// 入栈
void push(Stack* s, int x) {
if (isFull(s)) {
printf("Stack is full.\n");
return;
}
s->top++; // 栈顶指针加1
s->data[s->top] = x; // 将数据存储到栈顶位置
}
// 出栈
int pop(Stack* s) {
if (isEmpty(s)) {
printf("Stack is empty.\n");
return -1;
}
int x = s->data[s->top]; // 取出栈顶元素
s->top--; // 栈顶指针减1
return x;
}
// 获取栈顶元素
int peek(Stack* s) {
if (isEmpty(s)) {
printf("Stack is empty.\n");
return -1;
}
return s->data[s->top];
}
// 判断字符是否为操作符
int isOperator(char c) {
return c == '+' || c == '-' || c == '*' || c == '/';
}
// 计算表达式
int calculate(int a, int b, char op) {
switch (op) {
case '+': return a + b;
case '-': return a - b;
case '*': return a * b;
case '/': return a / b;
default: return 0;
}
}
// 计算表达式(后缀表达式)
int evaluate(char* postfix) {
Stack s;
initStack(&s);
char* p = postfix;
while (*p != '\0') {
if (*p >= '0' && *p <= '9') { // 如果是数字,将其入栈
int num = *p - '0';
while (*(p+1) >= '0' && *(p+1) <= '9') { // 处理多位数字
num = num * 10 + *(++p) - '0';
}
push(&s, num);
} else if (isOperator(*p)) { // 如果是操作符,弹出栈顶的两个数字进行计算
int b = pop(&s);
int a = pop(&s);
int result = calculate(a, b, *p);
push(&s, result);
}
p++;
}
return pop(&s); // 最后栈内只剩下一个结果,返回它
}
int main() {
char infix[100]; // 中缀表达式
printf("Enter an infix expression: ");
scanf("%s", infix);
// 将中缀表达式转换为后缀表达式
char postfix[100]; // 后缀表达式
Stack s;
initStack(&s);
char* p = infix;
char* q = postfix;
while (*p != '\0') {
if (*p >= '0' && *p <= '9') { // 如果是数字,直接输出到后缀表达式
*(q++) = *p;
} else if (*p == '(') { // 如果是左括号,入栈
push(&s, *p);
} else if (*p == ')') { // 如果是右括号,弹出栈内所有操作符并输出到后缀表达式,直到遇到左括号
while (!isEmpty(&s) && peek(&s) != '(') {
*(q++) = pop(&s);
}
pop(&s); // 弹出左括号
} else if (isOperator(*p)) { // 如果是操作符
while (!isEmpty(&s) && peek(&s) != '(' && ((*p == '+' || *p == '-') && (peek(&s) == '*' || peek(&s) == '/'))) { // 如果栈顶有更高优先级的操作符,则弹出栈顶操作符并输出到后缀表达式
*(q++) = pop(&s);
}
push(&s, *p); // 将当前操作符入栈
}
p++;
}
while (!isEmpty(&s)) { // 将栈内剩余的操作符输出到后缀表达式
*(q++) = pop(&s);
}
*q = '\0'; // 末尾添加结束符
printf("Postfix expression: %s\n", postfix);
int result = evaluate(postfix);
printf("Result: %d\n", result);
return 0;
}