算符优先算法(C++实现)

2018/9/1 posted in  Algorithm

源码

//
//  main.cpp
//  test
//
//  Created by 皂白 on 2018/9/1.
//  Copyright © 2018年 皂白. All rights reserved.
//

#include <iostream>
#include <stack>

using namespace std;

// 判断是否是运算符
bool isOperator(char ch)
{
    switch(ch)
    {
        case'+':
        case'-':
        case'*':
        case'/':
            return true;
        default:
            return false;
    }
}

// 判断运算符的优先级
int getPriority(char ch) {
    int priority = 1;
    if (ch == '+' || ch == '-')
        // 加减优先级为1
        priority = 1;
    else if (ch == '*' || ch == '/')
        // 乘除优先级为2
        priority = 2;
    return priority;
}

// 从数字栈中出栈两个数字
void getTwoNumFromStack(stack<int>& numberStack, int& first, int& second)
{
    second = numberStack.top();
    numberStack.pop();
    
    first = numberStack.top();
    numberStack.pop();
}

// 传入中缀表达式,获得后缀表达式
string getPostfixExpression(string& infix)
{
    // 定义运算符栈
    stack<char> operatorStack;
    
    // 定义后缀表达式字符串
    string postfix;
    
    // 循环中缀表达式的每个字符
    for (auto p : infix)
    {
        if (isOperator(p))
        {
            // 如果是运算符,并且当栈不为空,并且栈的顶部是运算符,并且栈顶部的运算符优先级比当前运算符的优先级高,
            // 就把栈的顶部的运算符出栈追加到后缀表达式,接着把当前运算符入栈
            while (!operatorStack.empty() && isOperator(operatorStack.top()) && getPriority(operatorStack.top()) >= getPriority(p))
            {
                postfix.push_back(operatorStack.top());
                postfix.push_back(' ');
                operatorStack.pop();
            }
            operatorStack.push(p);
        }
        else if (p == '(')
        {
            // 入栈 '('
            operatorStack.push(p);
        }
        else if (p == ')')
        {
            while (operatorStack.top() != '(')
            {
                // 当栈的顶端不是 '(' 时,一直循环把栈里面的内容追加到到后缀表达式
                postfix.push_back(operatorStack.top());
                postfix.push_back(' ');
                operatorStack.pop();
            }
            // 出栈 ‘(’
            operatorStack.pop();
        }
        else
        {
            // 把数字直接追加到后缀表达式
            postfix.push_back(p);
            postfix.push_back(' ');
        }
    }
    while (!operatorStack.empty())
    {
        // 再把栈里面的内容追加到后缀表达式
        postfix.push_back(operatorStack.top());
        postfix.push_back(' ');
        operatorStack.pop();
    }
    postfix.pop_back();
    return postfix;
}

// 计算后缀表达式的值
int calculatePostfix(string& postfix)
{
    // 定义参与运算的第一个和第二个数字
    int first, second;
    
    // 定义数字栈
    stack<int> numberStack;
    
    // 循环后缀表达式的每个字符
    for (auto p : postfix)
    {
        switch (p)
        {
            case '*':
                // 乘法
                getTwoNumFromStack(numberStack, first, second);
                numberStack.push(first * second);
                break;
            case '/':
                // 除法
                getTwoNumFromStack(numberStack, first, second);
                numberStack.push(first / second);
                break;
            case '+':
                // 加法
                getTwoNumFromStack(numberStack, first, second);
                numberStack.push(first + second);
                break;
            case '-':
                // 减法
                getTwoNumFromStack(numberStack, first, second);
                numberStack.push(first - second);
                break;
            case ' ':
                // 空格直接跳过
                break;
            default:
                // 如果是数字,把数字入栈
                numberStack.push(p - '0');
                break;
        }
    }
    
    // 获取结果
    int result = numberStack.top();
    numberStack.pop();
    return result;
}


int main() {
    string infix = "1+2*4";
    string infix2 = "(1+2)*4";
    string infix3 = "(1+2)*4-3";
    string infix4 = "(1+2)*4-3+3*(3+2)";
    cout << "中缀表达式: " << infix << endl;
    string postfix = getPostfixExpression(infix);
    cout << "后缀表达式: " << postfix << endl;
    cout << "求值: " << calculatePostfix(postfix) << endl;
    return 0;
}

参考资料