C++ 利用链栈 后缀表达式

后缀表达式也称为逆波兰表达式，是一种不含括号，运算符位于两个操作数之后的表达式。在计算机中，常用于进行算术运算、逻辑运算和函数计算等。

利用链栈来计算后缀表达式的步骤如下：

1. 创建一个空链栈，用于存储操作数。

2. 从左到右扫描后缀表达式中的每个元素，如果是操作数，则将其入栈。

3. 如果是操作符，则从栈中弹出两个操作数，并将其进行运算，将结果入栈。

4. 重复步骤2和3，直到扫描完整个后缀表达式。

5. 最后栈中只剩一个元素，即为后缀表达式的计算结果。

下面是一个利用链栈计算后缀表达式的示例代码：

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

typedef struct Node {
int data;
struct Node *next;
} Node, *LinkStack;

LinkStack createStack() {
LinkStack top = (LinkStack)malloc(sizeof(Node));
top->next = NULL;
return top;
}

int isEmpty(LinkStack top) {
return top->next == NULL;
}

void push(LinkStack top, int data) {
Node *p = (Node*)malloc(sizeof(Node));
p->data = data;
p->next = top->next;
top->next = p;
}

int pop(LinkStack top) {
if (isEmpty(top)) {
printf("Error: stack is empty!\n");
return -1;
}
Node *p = top->next;
int data = p->data;
top->next = p->next;
free(p);
return data;
}

int calculate(char *exp) {
LinkStack stack = createStack();
int i = 0;
while (exp[i] != '\0') {
if (exp[i] >= '0' && exp[i] <= '9') { // 操作数入栈
push(stack, exp[i] - '0');
} else if (exp[i] == '+' || exp[i] == '-' || exp[i] == '*' || exp[i] == '/') { // 运算符计算
int op2 = pop(stack);
int op1 = pop(stack);
int result;
switch (exp[i]) {
case '+': result = op1 + op2; break;
case '-': result = op1 - op2; break;
case '*': result = op1 * op2; break;
case '/': result = op1 / op2; break;
}
push(stack, result);
}
i++;
}
int result = pop(stack);
free(stack);
return result;
}

int main() {
char exp[] = "34+5*";
printf("%s = %d\n", exp, calculate(exp));
return 0;
}