[数据结构与算法]表达式计算C++

问题描述

给定四则运算（含括号）表达式，计算运算结果。
拓展知识：逆波兰式。

样例输入

3+4*(5+6)

样例输出

47

问题分析

四则运算基本法则：先算乘除，后算加减，有括号的先算括号。于是给运算符定义优先级：

由于括号实际上并不参与运算，只是改变运算的先后次序，所以括号不用考虑优先级，遇到括号时特判即可。

由于运算过程中，存在先算后面的情况，所以用栈来保存前面的运算符（如±），等后面运算（如*/）完成，再弹出栈中的运算符进行计算。这里的符号栈是单调栈，始终保持栈底到栈顶的符号优先级是递增的，因为栈顶内容最先被弹出并计算。

对于当前运算符，需要和栈顶元素比较优先级。如果栈顶优先级高，那就出栈运算；如果栈顶优先级低或相等，那就先入栈，因为不确定后面是不是还有优先级更高的符号。

光有符号栈还不够，数字也需要保存，所以就另外开辟一个数字栈来暂存数组，与符号栈同步。

代码实现

#include <bits/stdc++.h>
using namespace std;

// 定义符号的优先级
int priority(char oper)
{
    if (oper == '+' || oper == '-')
        return 1;
    if (oper == '*' || oper == '/')
        return 2;
}

// 进行一次计算
void calculate(stack<int> &nums, stack<char> &symbols)
{
    int b = nums.top();
    nums.pop();
    int a = nums.top();
    nums.pop();
    char oper = symbols.top();
    symbols.pop();
    if (oper == '+')
        nums.push(a + b);
    if (oper == '-')
        nums.push(a - b);
    if (oper == '*')
        nums.push(a * b);
    if (oper == '/')
        nums.push(a / b); // 整除
}

// 表达式计算,需要保证表达式合法
int expression_calculation(const string &s)
{
    stack<int> nums;
    stack<char> symbols;
    bool last_is_num = false; // 标记上一个元素是数字还是运算符
    for (int i = 0; i < s.length(); i++)
    {
        if (isdigit(s[i])) // 读取数字
        {
            int num = 0;
            for (; i < s.length() && isdigit(s[i]); i++)
                num = num * 10 + s[i] - '0';
            nums.push(num);
        }
        if (i >= s.length())
            break;

        cout << s[i] << endl;
        // 读取运算符，并考虑进行计算
        if (s[i] == ')') // 寻找左括号
        {
            while (symbols.top() != '(')
                calculate(nums, symbols);
            symbols.pop(); // 弹出(
        }
        else
        {
            while (!symbols.empty() && symbols.top() != '(' && s[i] != '(' &&
                   priority(symbols.top()) >= priority(s[i])) // 栈内的高或等优先级都可以计算了
                calculate(nums, symbols);
            symbols.push(s[i]); // 当前运算符入栈
        }
    }
    while (!symbols.empty()) // 栈中剩余运算符进行计算
        calculate(nums, symbols);
    return nums.top();
}

int main()
{
    string s = "3+4*(5+6)";
    int result = expression_calculation(s);
    cout << result << endl;
}

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖