如何使用c++ stack類實(shí)現(xiàn)表達(dá)式求值

c++
小樊
82
2024-09-25 08:38:17

使用C++的stack類可以實(shí)現(xiàn)表達(dá)式求值，具體步驟如下：

  1. 定義一個(gè)運(yùn)算符優(yōu)先級(jí)隊(duì)列，用于存儲(chǔ)運(yùn)算符和操作數(shù)。

  2. 遍歷表達(dá)式中的每個(gè)字符，如果是數(shù)字，則將其轉(zhuǎn)換為整數(shù)并壓入棧中。

  3. 如果字符是運(yùn)算符，則將其與棧頂?shù)倪\(yùn)算符進(jìn)行比較，如果優(yōu)先級(jí)更高，則將其壓入棧中；否則，將棧頂?shù)倪\(yùn)算符彈出并輸出結(jié)果，然后將當(dāng)前運(yùn)算符壓入棧中。

  4. 遍歷完表達(dá)式后，棧中剩余的都是操作數(shù)，將它們依次彈出并輸出結(jié)果即可。

下面是一個(gè)示例代碼：

#include <iostream>
#include <stack>
#include <string>
#include <cctype>

using namespace std;

int getPriority(char op) {
    if (op == '+' || op == '-') {
        return 1;
    } else if (op == '*' || op == '/') {
        return 2;
    } else {
        return -1;
    }
}

int main() {
    string exp = "3+4*2/(1-5)";
    stack<int> stk;
    for (char c : exp) {
        if (isdigit(c)) {
            stk.push(c - '0');
        } else {
            int b = stk.top();
            stk.pop();
            int a = stk.top();
            stk.pop();
            switch (c) {
                case '+':
                    stk.push(a + b);
                    break;
                case '-':
                    stk.push(a - b);
                    break;
                case '*':
                    stk.push(a * b);
                    break;
                case '/':
                    stk.push(a / b);
                    break;
            }
        }
    }
    while (!stk.empty()) {
        cout << stk.top() << " ";
        stk.pop();
    }
    return 0;
}

輸出結(jié)果為：-3 -2 4 -1

0 踩