用C语言写一个完整的算法,包含数据和输出结果。利用顺序栈的基本操作实现算术表达式求值。
时间: 2024-10-23 13:17:06 浏览: 24
在C语言中,我们可以使用顺序栈(数组实现)来计算简单的算术表达式。这里我将展示一个基本的中缀到后缀(Infix to Postfix)转换以及后缀表达式的求值过程。假设我们只处理加法、减法和乘法,且没有括号。
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX StackSize
typedef struct {
int top;
int data[MAX];
} Stack;
// 初始化栈
void init(Stack *s) {
s->top = -1;
}
// 判断栈是否为空
int isEmpty(Stack *s) {
return (s->top == -1);
}
// 入栈
void push(Stack *s, int x) {
if (isEmpty(s)) {
s->data[++(s->top)] = x;
}
}
// 出栈
int pop(Stack *s) {
if (isEmpty(s))
return INT_MIN;
return s->data[s->top--];
}
// 中缀表达式转后缀表达式
char* infixToPostfix(char* expression) {
char postfix[MAX], *p = postfix, op = '+';
Stack s;
init(&s);
for (int i = 0; expression[i]; ++i) {
if (expression[i] >= '0' && expression[i] <= '9') { // 非运算符字符
while (!isEmpty(&s) && precedence(op) <= precedence(expression[i])) {
*p++ = pop(&s);
}
*p++ = expression[i];
} else if (expression[i] == '(') { // 左括号,压入栈
push(&s, expression[i]);
} else if (expression[i] == ')') { // 右括号,弹出直到左括号
while (!isEmpty(&s) && pop(&s) != '(')
*p++ = pop(&s);
if (isEmpty(&s)) return NULL; // 配对错误
} else { // 运算符,先处理同优先级的
while (!isEmpty(&s) && precedence(op) == precedence(expression[i]))
*p++ = pop(&s);
push(&s, expression[i]); // 将当前运算符压入栈
}
}
while (!isEmpty(&s)) { // 处理剩余的运算符
*p++ = pop(&s);
}
*p = '\0'; // 结束标志
return postfix;
}
// 求后缀表达式的值
double evaluatePostfix(char* expression) {
double stack[MAX], result = 0;
Stack s;
init(&s);
for (int i = 0; expression[i]; ++i) {
if (expression[i] >= '0' && expression[i] <= '9') { // 整数直接入栈
stack[++(s.top)] = expression[i] - '0';
} else { // 运算符,从栈取出两个数并计算
double val1 = stack[s.top--];
double val2 = stack[s.top--];
switch (expression[i]) {
case '+':
result = val2 + val1;
break;
case '-':
result = val2 - val1;
break;
case '*':
result = val2 * val1;
break;
default:
printf("Invalid operator.\n");
return 0;
}
stack[s.top++] = result;
}
}
return stack[0];
}
int main() {
char expression[] = "2+3*4";
char* postfix = infixToPostfix(expression);
if (postfix) {
printf("Postfix expression: %s\n", postfix);
double value = evaluatePostfix(postfix);
printf("Result: %.2f\n", value);
free(postfix);
} else {
printf("Error in conversion.\n");
}
return 0;
}
阅读全文