记得去年刚上大一的时候,有一次实验课的作业就是做一个计算器。我当时就是想实现计算任意的四则运算表达式的功能。我依稀记得当时的实现非常的复杂,还用了正则表达式去匹配,获得相应的元素。但是当时没能实现处理括号的问题,只要不包含括号的算式,我当时都能解决。当时真的是想破脑袋都没想出来怎么解决这个问题。

然后直到现在看到数据结构这本书上面讲了,我才明白,赶紧按照书上的思路自己敲个代码来试试看。

逆波兰表达式

逆波兰表达式也称为后缀表达式,简单但不完全正确的说,就是把符号移到数字的后面。其实准确的说是遇到数字就压入栈,遇到符号就把栈顶的两个元素给弹出来,然后应用相应的计算过程,再把结果压入栈,直到最后就可以得到最终结果(最终状态下的栈顶元素,此时栈大小为1)

比如:4.99*1.06+5.99+6.99*1.06的逆波兰表达式是4.99 1.06 * 5.99 + 6.99 1.06 * +

将普通表达式转为逆波兰表达式

我们发现逆波兰表达式的计算过程非常简单,那么我们怎么把普通表达式转为逆波兰表达式呢?

方法:创建一个队列和一个栈。

遇到数字就压入队列,遇到符号就入栈。

对于符号的处理,有以下规则:

  1.  括号特殊处理,正括号优先级最高,副括号优先级最低,遇到副括号就往回找正括号。
  2.  其他符号根据优先级,若栈顶元素的优先级大于等于当前符号的优先级,且不是正括号 ==》 一直弹出,直到栈顶元素优先级比当前符号的低,然后把当前元素压入栈

弹出的符号除了括号外,都压入队列。

最终从依次队列首部取出元素,得到的就是逆波兰表达式了。

这很简单,看代码就行了。

代码:

#include <iostream>
#include<stack>
#include "string"
#include "sstream"
#include<queue>
#include "map"

using namespace std;

map<char, int> mp;

void init_priority() {
    //定义优先级
    mp['('] = 3;
    mp[')'] = 0;
    mp['+'] = mp['-'] = 1;
    mp['*'] = mp['/'] = 2;
}

//截取字符串
string sub_str(const string &s, int st, int end) {
    stringstream ss;
    for (int i = st; i <= end; ++i)
        ss << s[i];
    string tmp = ss.str();
    //cout<<tmp<<endl;
    return tmp;
}

//生成逆波兰表达式
/**
 * 数字直接加入表达式
 * 符号入栈规则:
 *      1、括号特殊处理,正括号优先级最高,副括号优先级最低,遇到副括号就往回找正括号。
 *      2、其他符号根据优先级,若栈顶元素的优先级大于等于当前符号的优先级,且不是正括号 ==》 一直弹出,直到栈顶元素优先级比当前符号的低,
 *          然后把当前元素压入栈
 * @param s
 * @return
 */
queue<string> generate_expression(string s) {
    stack<char> stk;
    queue<string> expression;//逆波兰表达式存储在这里

    int last_idx = 0;
    stringstream ss;
    for (int i = 0; i < s.length(); ++i) {
        if (s[i] == '(') {
            if (last_idx <= i - 1)
                expression.push(sub_str(s, last_idx, i - 1));
            stk.push(s[i]);
            last_idx = i + 1;
        } else if (s[i] == ')') {
            if (last_idx <= i - 1)
                expression.push(sub_str(s, last_idx, i - 1));
            while (!stk.empty() && stk.top() != '(') {

                ss << stk.top();
                expression.push(ss.str());
                ss.clear();
                ss.str("");
                stk.pop();
            }
            stk.pop();
            last_idx = i + 1;
        } else if (s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/') {
            if (last_idx <= i - 1)
                expression.push(sub_str(s, last_idx, i - 1));

            if (!stk.empty() && mp[s[i]] <= mp[stk.top()] && stk.top() != '(') {
                while (!stk.empty() && mp[s[i]] <= mp[stk.top()] && stk.top() != '(') {
                    ss << stk.top();
                    expression.push(ss.str());
                    ss.clear();
                    ss.str("");
                    stk.pop();
                }

            }
            stk.push(s[i]);
            last_idx = i + 1;
        }

    }
    int dis = s.length() - last_idx - 1;
    if (dis >= 0) {
        expression.push(sub_str(s, last_idx, s.length() - 1));
    }
    while (!stk.empty()) {
        ss << stk.top();
        expression.push(ss.str());
        ss.clear();
        ss.str("");
        stk.pop();
    }


    return expression;
}

pair<double, double> get_num(stack<double> &stk) {

    double a, b;
    a = stk.top(), stk.pop();
    b = stk.top(), stk.pop();
    return make_pair(a, b);
}

double calculate(queue<string> expression) {
    double ans = 0;
    stack<double> stk;
    bool err_flag = false;
    while (!expression.empty()) {
        if (expression.front() == "+") {
            if (stk.size() < 2) {
                err_flag = true;
                break;
            }
            auto p = get_num(stk);
            stk.push(p.first + p.second);
        } else if (expression.front() == "-") {
            if (stk.size() < 2) {
                err_flag = true;
                break;
            }
            auto p = get_num(stk);
            stk.push(p.first - p.second);
        } else if (expression.front() == "*") {
            if (stk.size() < 2) {
                err_flag = true;
                break;
            }
            auto p = get_num(stk);
            stk.push(p.first * p.second);
        } else if (expression.front() == "/") {
            if (stk.size() < 2) {
                err_flag = true;
                break;
            }
            auto p = get_num(stk);
            stk.push(p.second / p.first);
        } else {
            //压入数字
            stk.push(atof(expression.front().c_str()));
        }
        expression.pop();
    }

    if (err_flag || stk.size() != 1) {
        cout << "表达式存在错误!" << endl;
        exit(0);
    } else
        return stk.top();
}

int main() {

    //初始化运算符的优先级
    init_priority();

    cout << "请输入算式:\n>> ";
    string s;
    cin >> s;
    queue<string> expression = generate_expression(s);
    queue<string> tmp = expression;
    cout << "逆波兰表达式:";
    while (!tmp.empty()) {
        cout << tmp.front() << ' ';
        tmp.pop();
    }
    cout << endl;

    cout << "结果:" << calculate(expression) << endl;
    return 0;
}

转载请注明来源:https://www.longjin666.top/?p=1165

欢迎关注我的公众号“灯珑”,让我们一起了解更多的事物~

你也可能喜欢

发表评论