王道計算機(jī)考研 數(shù)據(jù)結(jié)構(gòu)
P29 中綴表達(dá)式的計算（順序棧實現(xiàn)）
#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;
}
// 判斷是否為數(shù)字 (isdigit函數(shù))?
bool isNumberChar(char c) {
return c >= '0' && c <= '9';
}
// 判斷是否為運(yùn)算符?
bool is_operator(char c) {
return (c == '+' || c == '-' || c == '*' || c == '/');
}
// 判斷運(yùn)算符優(yōu)先級?
int precedence(char c) {
switch(c) {
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
default:
return 0;
}
}
// 解析數(shù)字(atof函數(shù))?
double parseNumber(const char *expression, int *index) {
double num = 0.0;
int i = *index;
// // 解析整數(shù)部分
while(isNumberChar(expression[i])) {
num = num * 10 + (expression[i] - '0');
i++;
}
// // 解析小數(shù)部分
if (expression[i] == '.') {
i++;??// 跳過小數(shù)點
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])) {
//?跳過當(dāng)前數(shù)字字符（或操作符）的部分，直到遇到空格或字符串結(jié)束符 '\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：該算法沒有處理負(fù)數(shù)的情況，有些地方可能有些冗余，不對之處歡迎指正
