逆波兰法-算术表达式语法分析C++

逆波兰表达式的C++实现。算术表达式求值，支持加减乘除和幂运算，支持圆括号改变优先级。

//后缀表达式练习
//2018-09-20
#include <stack>
#include <iostream>
#include <cstdlib>
#include <string>
#include <math.h>
using namespace std;
//定义优先级
enum Priority {
    PRI_IGNORE,//无效字符，忽略
    PRI_NUMBER,//操作数
    PRI_PLUS,//加减
    PRI_DIVIDE,//乘除
    PRI_POWER,//幂
    PRI_LEFT_PAR,//左圆括号
    PRI_RIGTHT_PAR,//右圆括号
};
//取操作符优先级
Priority getPriority(char symbol) {
    if ((symbol >= '0' && symbol <= '9') || symbol == '.')
        return PRI_NUMBER;
    else if (symbol == '+' || symbol == '-')
        return PRI_PLUS;
    else if (symbol == '*' || symbol == '/')
        return PRI_DIVIDE;
    else if (symbol == '^')
        return PRI_POWER;
    else if (symbol == '(')
        return PRI_LEFT_PAR;
    else if (symbol == ')')
        return PRI_RIGTHT_PAR;
    else
        return PRI_IGNORE;
}
//中缀表达式转后缀表达式
string toSufixExpression(string express) {
    stack<char> operendStack;//操作符暂存栈
    string output;//输出后缀表达式
    //上一操作符的优先级，如果当前处理的操作符优先级低于它则前操作符出栈
    Priority lastPriority = PRI_NUMBER;
    string::iterator iter = express.begin();
    for (; iter != express.end(); ++iter) {
        Priority priority = getPriority(*iter);
        switch (priority) {
        case PRI_IGNORE:
        default:
            continue;
        case PRI_NUMBER:
            output.push_back(*iter);
            break;
        case PRI_PLUS:
        case PRI_DIVIDE:
        case PRI_POWER:
        case PRI_LEFT_PAR:
            //遇到符号向前追加间隔符
            output.push_back(' ');
            while (operendStack.size()) {
                if (getPriority(operendStack.top()) < priority || operendStack.top() == '(')
                    break;
                output.push_back(operendStack.top());
                operendStack.pop();
            }
            lastPriority = priority;
            operendStack.push(*iter);
            break;
        case PRI_RIGTHT_PAR:
            while (operendStack.size()) {
                if (operendStack.top() != '(') {
                    output.push_back(operendStack.top());
                    operendStack.pop();
                }
                else {
                    operendStack.pop();
                    break;
                }
            }
            break;
        }
    }
    //处理完毕，剩余操作符出栈
    while (operendStack.size()) {
        output.push_back(operendStack.top());
        operendStack.pop();
    }
    return output;
}
//计算后缀表达式
double caculate(string express) {
    stack<double> calcStack;//计算存储栈
    string::iterator iter = express.begin();
    while (iter != express.end()) {
        //字符串转整形，并压入栈
        if (*iter >= '0' && *iter <= '9') {
            string number;
            do {
                number.push_back(*iter);
                ++iter;
            } while ((*iter >= '0' && *iter <= '9') || *iter == '.');
            calcStack.push(atoi(number.c_str()));
            continue;
        }
        //间隔符
        if (*iter == ' ') {
            ++iter;
            continue;
        }
        //操作符，执行运算
        if (calcStack.size() < 2)
            return 0;
        double operandOne = calcStack.top();
        calcStack.pop();
        double operandTwo = calcStack.top();
        calcStack.pop();
        switch (*iter++) {
        case '+':
            calcStack.push(operandTwo + operandOne);
            break;
        case '-':
            calcStack.push(operandTwo - operandOne);
            break;
        case '*':
            calcStack.push(operandTwo * operandOne);
            break;
        case '/':
            calcStack.push(operandTwo / operandOne);
            break;
        case '^':
            calcStack.push(pow(operandTwo, operandOne));
            break;
        default:
            calcStack.push(operandTwo);
            calcStack.push(operandOne);
            break;
        }
    }
    if (calcStack.size() == 1)
        return calcStack.top();
    return 0;
}

int main() {
    cout << "Please enter an expression:" << endl;
    string express;//表达式
    getline(cin, express);
    if (express.empty()) {
        cout << "empty express.\n";
        return 0;
    }
    string output = toSufixExpression(express);
    cout << caculate(output) << endl;
    system("pause");
    return 0;
}