堆疊的應用——運算式求值

題目描述

給定一個運算式，其中運算子僅包含 +,-,*,/（加減乘整除），可能包含括號，請你求出運算式的最終值，
注意：

資料保證給定的運算式合法，
題目保證符號 - 只作為減號出現，不會作為負號出現，例如，-1+2,(2+2)*(-(1+1)+2) 之類運算式均不會出現，
題目保證運算式中所有數字均為正整數，
題目保證運算式在中間計算程序以及結果中，均不超過 2^31?1，
題目中的整除是指向 0 取整，也就是說對于大于 0 的結果向下取整，例如 5/3=1，對于小于 0 的結果向上取整，例如5/(1?4)=?1，
C++和Java中的整除默認是向零取整；Python中的整除//默認向下取整，因此Python的eval()函式中的整除也是向下取整，在本題中不能直接使用，
原題鏈接：https://www.acwing.com/problem/content/description/3305/

解題思路

首先考慮符號的優先級 “)” > “/” == “*” > “+” == “-” > “(”
因為之后有優先級的比較所以我這里用一個hash表來存盤優先級的高低

unordered_map<char, int> pr{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};

明確思路：
STEP 1：先將算術運算式轉換成后綴運算式，
STEP 2：然后對該后綴運算式求值，

完整代碼

#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>
#include <unordered_map>

using namespace std;

stack<int> num;
stack<char> op;

void eval()
{
    auto b = num.top(); num.pop();
    auto a = num.top(); num.pop();
    auto c = op.top(); op.pop();
    int x;
    if (c == '+') x = a + b;
    else if (c == '-') x = a - b;
    else if (c == '*') x = a * b;
    else x = a / b;
    num.push(x);
}

int main()
{
    unordered_map<char, int> pr{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
    string str;
    cin >> str;
    for (int i = 0; i < str.size(); i ++ )
    {
        auto c = str[i];
        if (isdigit(c))
        {
            int x = 0, j = i;
            while (j < str.size() && isdigit(str[j]))
                x = x * 10 + str[j ++ ] - '0';
            //這里是因為我們將數字差分為字符所以12會被差分為'1'和'2'
            i = j - 1;
            num.push(x);
        }
        else if (c == '(') op.push(c);
        //遇到左括號直接入堆疊
        else if (c == ')')
        {
            while (op.top() != '(') eval();
            op.pop();
        }
        else
        {
            while (op.size() && op.top() != '(' && pr[op.top()] >= pr[c]) eval();
            op.push(c);
        }
    }
    while (op.size()) eval();
    cout << num.top() << endl;
    return 0;
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/279583.html

標籤：其他

上一篇：華為大佬親筆全網最全的Redis資料結構及適用場景詳解

下一篇：c語言檔案的基本操作