第1关：基于栈的中缀算术表达式求值,用c++编写

#include <stdio.h>
#include <stdlib.h>

/* 栈结构体 */
typedef struct stack {
int top;
int capacity;
int *array;
} Stack;

/* 创建栈 */
Stack *createStack(int capacity) {
Stack *stack = (Stack *)malloc(sizeof(Stack));
stack->top = -1;
stack->capacity = capacity;
stack->array = (int *)malloc(stack->capacity * sizeof(int));
return stack;
}

/* 判断栈是否已满 */
int isFull(Stack *stack) {
return stack->top == stack->capacity - 1;
}

/* 判断栈是否为空 */
int isEmpty(Stack *stack) {
return stack->top == -1;
}

/* 压栈 */
void push(Stack *stack, int item) {
if (isFull(stack)) {
printf("Stack is full\n");
return;
}
stack->array[++stack->top] = item;
}

/* 出栈 */
int pop(Stack *stack) {
if (isEmpty(stack)) {
printf("Stack is empty\n");
return -1;
}
return stack->array[stack->top--];
}

/* 获取栈顶元素 */
int peek(Stack *stack) {
if (isEmpty(stack))
return -1;
return stack->array[stack->top];
}

/* 操作符优先级 */
int precedence(char ch) {
switch (ch) {
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
case '^':
return 3;
default:
return -1;
}
}

/* 中缀表达式求值 */
int evaluate(char *exp) {
Stack *operands = createStack(strlen(exp));
Stack *operators = createStack(strlen(exp));
for (int i = 0; exp[i]; ++i) {
if (exp[i] == ' ')
continue;
else if (isdigit(exp[i])) {
int num = 0;
while (isdigit(exp[i])) {
num = num * 10 + (exp[i] - '0');
++i;
}
--i;
push(operands, num);
}
else if (exp[i] == '(')
push(operators, exp[i]);
else if (exp[i] == ')') {
while (!isEmpty(operators) && peek(operators) != '(') {
int op1 = pop(operands);
int op2 = pop(operands);
char op = pop(operators);
switch (op) {
case '+':
push(operands, op2 + op1);
break;
case '-':
push(operands, op2 - op1);
break;
case '*':
push(operands, op2 * op1);
break;
case '/':
push(operands, op2 / op1);
break;
case '^':
push(operands, pow(op2, op1));
break;
}
}
if (!isEmpty(operators) && peek(operators) == '(')
pop(operators);
}
else {
while (!isEmpty(operators) && precedence(exp[i]) <= precedence(peek(operators))) {
int op1 = pop(operands);
int op2 = pop(operands);
char op = pop(operators);
switch (op) {
case '+':
push(operands, op2 + op1);
break;
case '-':
push(operands, op2 - op1);
break;
case '*':
push(operands, op2 * op1);
break;
case '/':
push(operands, op2 / op1);
break;
case '^':
push(operands, pow(op2, op1));
break;
}
}
push(operators, exp[i]);
}
}
while (!isEmpty(operators)) {
int op1 = pop(operands);
int op2 = pop(operands);
char op = pop(operators);
switch (op) {
case '+':
push(operands, op2 + op1);
break;
case '-':
push(operands, op2 - op1);
break;
case '*':
push(operands, op2 * op1);
break;
case '/':
push(operands, op2 / op1);
break;
case '^':
push(operands, pow(op2, op1));
break;
}
}
return pop(operands);
}

int main() {
char exp[] = "3 + 4 * ( 5 - 2 ) ^ 2";
printf("结果为：%d\n", evaluate(exp));
return 0;
}