王道计算机考研 数据结构
P29 中缀表达式的计算（顺序栈实现）
#include <stdio.h>
#include <stdbool.h>
#define MaxSize 30
typedef struct {
char data[MaxSize];
int top;
}Stack;
typedef struct {
double data[MaxSize];
int top;
}SqStack;
void initStack(Stack *S) {
S->top = -1;
}
void InitStack(SqStack *S) {
S->top = -1;
}
bool stackEmpty(Stack S) {
return S.top == -1;
}
bool StackEmpty(SqStack S) {
return S.top == -1;
}
bool pushOperator(Stack *S, char element) {
if (S->top > MaxSize - 1)
return false;
S->top++;
S->data[S->top] = element;
}
bool pushFigure(SqStack *S, double x) {
if (S->top == MaxSize - 1) return false;
S->top++;
S->data[S->top] = x;
return true;
}
char popOperator(Stack *S) {
if (S->top >= 0) {
return S->data[S->top--];
}
return '\0';
}
bool popFigure(SqStack *S, double *x) {
if (S->top == -1) return false;
*x = S->data[S->top];
S->top--;
return true;
}
// 判断是否为数字 (isdigit函数)
bool isNumberChar(char c) {
return c >= '0' && c <= '9';
}
// 判断是否为运算符
bool is_operator(char c) {
return (c == '+' || c == '-' || c == '*' || c == '/');
}
// 判断运算符优先级
int precedence(char c) {
switch(c) {
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
default:
return 0;
}
}
// 解析数字(atof函数)
double parseNumber(const char *expression, int *index) {
double num = 0.0;
int i = *index;
// // 解析整数部分
while(isNumberChar(expression[i])) {
num = num * 10 + (expression[i] - '0');
i++;
}
// // 解析小数部分
if (expression[i] == '.') {
i++; // 跳过小数点
double decimalValue = 0.0;
double decimalPlaceValue = 0.1;
while(isNumberChar(expression[i])) {
decimalValue = decimalValue + (expression[i] - '0') * decimalPlaceValue;
decimalPlaceValue *= 0.1;
i++;
}
num = num + decimalValue;
}
*index = i;
return num;
}
void tool(SqStack *S, char c) {
if ((c == '+' || c == '-' || c == '*' || c == '/')) {
double num1;
double num2;
popFigure(S, &num2);
popFigure(S, &num1);
switch (c) {
case '+':
pushFigure(S, num1 + num2);
break;
case '-':
pushFigure(S, num1 - num2);
break;
case '*':
pushFigure(S, num1 * num2);
break;
case '/':
pushFigure(S, num1 /num2);
break;
}
}
}
double calculate(const char *expression) {
Stack operatorStack;
initStack(&operatorStack);
SqStack S;
InitStack(&S);
int i = 0;
while (expression[i] != '\0') {
if (expression[i] == ' ') {
i++;
continue;
} else if (isNumberChar(expression[i])) {
double num = parseNumber(expression, &i);
pushFigure(&S, num);
while (isNumberChar(expression[i])) {
// 跳过当前数字字符（或操作符）的部分，直到遇到空格或字符串结束符 '\0'
i++;
}
i--;
} else if (expression[i] == '(') {
pushOperator(&operatorStack, expression[i]);
} else if (expression[i] == ')') {
while (operatorStack.top >= 0 && operatorStack.data[operatorStack.top] != '(') {
tool(&S, popOperator(&operatorStack));
}
popOperator(&operatorStack); // Pop '(' from stack
} else if (is_operator(expression[i])) {
while (operatorStack.top >= 0 && precedence(operatorStack.data[operatorStack.top]) >= precedence(expression[i])) {
tool(&S, popOperator(&operatorStack));
}
pushOperator(&operatorStack, expression[i]);
}
i++;
}
while (!stackEmpty(operatorStack)) {
tool(&S, popOperator(&operatorStack));
}
double result;
popFigure(&S, &result);
return result;
}
int main() {
const char *infixExpression = "((15/(7-(1+1)))*3)-(2+(1+1))";
double result = calculate(infixExpression);
printf("Result: %.2f\n", result);
return 0;
}
PS：该算法没有处理负数的情况，有些地方可能有些冗余，不对之处欢迎指正
