溫馨提示×

c語言怎么用棧實現表達式求值

小億
108
2023-12-12 15:56:17
欄目: 編程語言

使用棧實現表達式求值的一般方法如下：

1.定義兩個棧，一個用于存儲操作數，另一個用于存儲操作符。

2.遍歷表達式中的每個字符，按照以下規(guī)則處理：

  • 如果字符是操作數，則將其轉換為整數，并將其壓入操作數棧中。

  • 如果字符是操作符，則按照以下步驟處理：

    • 如果操作符棧為空，或者操作符棧的棧頂操作符為左括號’('，則將操作符壓入操作符棧中。
    • 如果操作符棧不為空，并且棧頂操作符的優(yōu)先級大于等于當前操作符的優(yōu)先級，則從操作數棧中彈出兩個操作數， 從操作符棧中彈出一個操作符，進行計算并將結果壓入操作數棧中，重復該步驟直到操作符棧為空， 或者棧頂操作符的優(yōu)先級小于當前操作符的優(yōu)先級，然后將當前操作符壓入操作符棧中。
    • 如果當前操作符為右括號’)‘，則從操作數棧中彈出兩個操作數，從操作符棧中彈出一個操作符， 進行計算并將結果壓入操作數棧中，重復該步驟直到遇到左括號’('，然后將左括號從操作符棧中彈出。

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];
}

// 獲取操作符的優(yōu)先級
int getPriority(char op) {
    switch (op) {
        case '+':
        case '-':
            return 1;
        case '*':
        case '/':
            return 2;
        default:
            return 0;
    }
}

// 執(zhí)行計算
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; // 用于處理負數

0 踩