C/C++ 表达式求值（含多位数）

个人主页：仍有未知等待探索_C语言疑难,数据结构,算法-CSDN博客

专题分栏：算法_仍有未知等待探索的博客-CSDN博客

目录

一、前言

二、解析

分析

最后直接上代码！

一、前言

表达式求值是一个比较基础的代码关于栈的使用。在写的时候充分锻炼了大脑的思维和对代码的调试能力。

如果是在纸上给一个计算表达式，你一定可以算出来，但是要用代码实现的时候就会感觉没什么思路了，接下来就来看我给你“操作一番”！

二、解析

分析

首先，从比较简单的表达式开始，看这个表达式是如何进行计算的。

?一开始，我们需要两个栈，一个用来存储操作数，另外一个用来存储运算符栈。

表达式用一个string类型进行存储（c语言的话，用一个char类型的数组也行）。然后依次遍历每个元素。

1. 先判断这个元素是不是数字，如果是的话，就直接进操作数栈。
2. 如果这个元素是左括号的话‘（?’ 就直接进入符号栈（括号的优先级比普通的运算符高）
3. 如果这个元素是右括号的话‘）’ 就依次把计算（也就是操作数栈弹出两个数，符号栈弹出一个符号）直到符号栈的栈顶是左括号，把左括号出栈，然后结束循环。
4. 如果这个元素是普通符号的话，就需要判断一下符号的优先级，如果要入栈的符号优先级高的话，就直接压栈；否则就是先计算然后再进行压栈。
5. 最后就是计算剩在栈里面的数，直到符号栈为空，操作数栈只剩一个数。然后把这个数输出来就行。

最后直接上代码！

#include <iostream>
using namespace std;
#include <stack>
#include <unordered_map>
#include <string>

stack<int>num;
stack<char>op;
string str;

// 存储运算符的优先级，等价于将一个；‘+’ == 1
unordered_map<char, int>pr = { {'+', 1}, {'-', 1}, {'*', 2}, {'/', 2} };

// 计算函数
void eval()
{
    // 从操作数栈弹出两个数，弹出的第一个数是双目操作符右边的数，要注意
    int a = num.top(); num.pop();
    int b = num.top(); num.pop();
    // 从符号栈弹出一个符号
    char opp = op.top(); op.pop();
    // 计算
    int c = 0;
    if (opp == '+') c = b + a;
    else if (opp == '-') c = b - a;
    else if (opp == '*') c = b * a;
    else if (opp == '/') c = b / a;
    // 将得数进行压栈操作
    num.push(c);
}

int main()
{
    // C++ 输入输出的加速语句
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    // 读入表达式
    cin >> str;
    
    for (int i = 0; i < str.size(); i++)
    {
        // auto 是一个关键字，系统可以根据后面赋值的数据类型自动进行匹配类型
        auto c = str[i];
        // 判断这个字符是不是数字
        if (isdigit(c))
        {
            auto j = i;
            int x = 0;
            // 如果这个数字的后面还是数字的话，证明数字不止一位，要进行加权操作
            while (j < str.size() && isdigit(str[j]))
            {
                x = x * 10 + str[j] - '0';
                j++;
            }
            // 将i移到j - 1的位置上，因为j在最后一个循环中+1操作了
            // j的位置现在是在相当于第一个不是数字的位置上，然后这个判断语句结束后，
            // i会继续+1，所以i要移到j前一个位置上，来让下一个循环到指定的位置上
            i = j - 1;
            num.push(x);
        }
        else if (c == '(') op.push(c);// 遇到左括号直接压栈
        else if (c == ')')// 遇到右括号，计算到符号栈栈顶是左括号，然后左括号出栈
        {
            while (op.size() && op.top() != '(') eval();
            op.pop();
        }
        else// 一般情况，注意一定是while循环，不懂的可以去搜一下表达式树，方便理解
        {
            while (op.size() && pr[op.top()] >= pr[c]) eval();
            op.push(c);
        }
    }
    // 处理最后栈里的元素
    while (op.size()) eval();
    // 输出栈顶元素
    cout << num.top() << endl;

    return 0;
}