博客

用双栈实现表达式，与之前不同的是加入了单目运算符，用c++实现可能麻烦了些

当然，我写的不一定全部样例都过，发现还请指正。


java原文

#include <iostream>
#include "cstdio"
#include "map"
#include "string"
#include "list"
#include "stack"
#include "queue"
#include "cmath"

using namespace std;
map<string, int> priority{
        {"+",   10},
        {"-",   10},
        {"*",   8},
        {"/",   8},
        {"sin", 6},
        {"cos", 6},
        {"tan", 6},
        {"lg",  6},
        {"ln",  6},
        {"(",   4},
        {")",   4}
};

bool isNumber(string str) {
    /**
     * 简单判断是否数字
     */
    int index = str.find('0') + str.find('1') + str.find('2') + str.find("3") + str.find('4') + str.find('5')
                + str.find('6') + str.find('7') + str.find('8') + str.find('9');
    return index != -10;
}

list<string> splitStr(string resource, string str) {
    /**
     * 以str分割resource
     */
    list<string> elements, elements_;;
    while (true) {
        int pos = resource.find(str);
        if (pos == -1) {
            if (str != "")
                elements.push_back(resource);
            break;
        }
        string left = resource.substr(0, pos);
        if (!left.empty()) {
            elements.push_back(left);
        }
        elements.push_back(str);
        resource.erase(resource.begin(), resource.begin() + pos + str.size());
    }
    for (list<string>::iterator it = elements.begin(); it != elements.end(); it++) {
        if (*it == "")
            continue;
        elements_.push_back(*it);
    }
    return elements_;
}

list<string> getElement(string resource) {
    /*
     * 将表达式拆成原子
     */
    list<string> elements;
    elements.push_back(resource);
    for (auto itMap = priority.begin(); itMap != priority.end(); itMap++) {
        list<string> temp1;
        for (auto itList = elements.begin(); itList != elements.end(); itList++) {
            temp1.splice(temp1.end(), splitStr(*itList, itMap->first));
        }
        elements.clear();
        elements.splice(elements.end(), temp1);
        temp1.clear();
    }
    return elements;
}

void single_operator(string str, stack<double> &nums) {
    /*
     * 单目运算符操作
     */
    double x = nums.top();
    nums.pop();
    if (str == "sin") {
        nums.push(sin(x));
    } else if (str == "cos") {
        nums.push(cos(x));
    } else if (str == "tan") {
        nums.push(tan(x));
    } else if (str == "lg") {
        nums.push(log10(x));
    } else if (str == "ln") {
        nums.push(log(x));
    } else {
        nums.push(0);
        cout << "error " + str << endl;
    }
}

void double_operator(string str, stack<double> &operatorNum) {
    /*
     * 双目运算符操作
     */
    char c = str[0];
    double x, y;
    y = operatorNum.top();
    operatorNum.pop();
    x = operatorNum.top();
    operatorNum.pop();
    switch (c) {
        case '+' :
            operatorNum.push(x + y);
            break;
        case '-':
            operatorNum.push(x - y);
            break;
        case '*':
            operatorNum.push(x * y);
            break;
        case '/':
            operatorNum.push(x / y);
            break;
        default:
            operatorNum.push(0);
    }
}

void cal_Num(string str, stack<double> &operatorNum) {
    /*
     * 计算简单表达式
     */
    if (priority[str] == 6)
        single_operator(str, operatorNum);
    else
        double_operator(str, operatorNum);
}

string strip(string str) {
    /*
     * 去除首尾空格
     */
    while (str[0] == ' ') {
        str.erase(str.begin());

    }
    while (str[str.size() - 1] == ' ') {
        str.erase(str.begin());
    }
    return str;
}

int main() {
    queue<string> re_queue;
    stack<string> operatorStr;
    stack<double> operatorNum;
    string resource;
    cin >> resource;
    list<string> l = getElement(resource);
    for (list<string>::iterator it = l.begin(); it != l.end(); it++) {
        re_queue.push(*it);
    }
    // 双栈表达式解析
    while (!re_queue.empty()) {
        string str = strip(re_queue.front());
        re_queue.pop();
        if (isNumber(str)) {
            operatorNum.push(stod(str));
            continue;
        }
        if (operatorStr.empty()) {
            operatorStr.push(str);
            continue;
        }
        if (str == "(") {
            operatorStr.push(str);
            continue;
        }
        if (str != ")") {
            if (priority[str] < priority[operatorStr.top()] || operatorStr.top() == "(") {
                operatorStr.push(str);
                continue;
            }
            cal_Num(operatorStr.top(), operatorNum);
            operatorStr.pop();
            operatorStr.push(str);
            continue;
        }
        while (operatorStr.top() != "(" && !operatorStr.empty()) {
            cal_Num(operatorStr.top(), operatorNum);
            operatorStr.pop();
        }
        operatorStr.pop();
    }
    while (!operatorStr.empty()) {
        cal_Num(operatorStr.top(), operatorNum);
        operatorStr.pop();
    }
    printf("%0.6f", operatorNum.top());
}