使用棧實現表達式求值的一般方法如下:
1.定義兩個棧,一個用于存儲操作數,另一個用于存儲操作符。
2.遍歷表達式中的每個字符,按照以下規則處理:
如果字符是操作數,則將其轉換為整數,并將其壓入操作數棧中。
如果字符是操作符,則按照以下步驟處理:
3.遍歷完整個表達式后,檢查操作符棧是否為空,如果不為空,則從操作數棧中彈出兩個操作數, 從操作符棧中彈出一個操作符,進行計算并將結果壓入操作數棧中,直到操作符棧為空。
4.最后,操作數棧中剩下的唯一一個元素就是表達式的最終結果。
以下是一個使用棧實現表達式求值的示例代碼:
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#define MAX_SIZE 100
// 定義棧結構
typedef struct {
int data[MAX_SIZE];
int top;
} Stack;
// 初始化棧
void initStack(Stack* s) {
s->top = -1;
}
// 判斷棧是否為空
int isEmpty(Stack* s) {
return s->top == -1;
}
// 判斷棧是否已滿
int isFull(Stack* s) {
return s->top == MAX_SIZE - 1;
}
// 元素入棧
void push(Stack* s, int val) {
if (isFull(s)) {
printf("Stack is full!\n");
return;
}
s->data[++s->top] = val;
}
// 元素出棧
int pop(Stack* s) {
if (isEmpty(s)) {
printf("Stack is empty!\n");
return -1;
}
return s->data[s->top--];
}
// 獲取棧頂元素
int top(Stack* s) {
if (isEmpty(s)) {
printf("Stack is empty!\n");
return -1;
}
return s->data[s->top];
}
// 獲取操作符的優先級
int getPriority(char op) {
switch (op) {
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
default:
return 0;
}
}
// 執行計算
int calculate(int num1, int num2, char op) {
switch (op) {
case '+':
return num1 + num2;
case '-':
return num1 - num2;
case '*':
return num1 * num2;
case '/':
return num1 / num2;
default:
return 0;
}
}
// 使用棧求解表達式的值
int evaluateExpression(char* expression) {
Stack numStack; // 操作數棧
Stack opStack; // 操作符棧
initStack(&numStack);
initStack(&opStack);
int num = 0; // 用于處理多位數
int sign = 1; // 用于處理負數