实验3-栈的应用-表达式求值

1、实验目的：

• 掌握栈的定义及实现；
• 掌握利用栈求解算术表达式的方法。

2、实验内容：

• 通过修改完善教材中 P78-79 的算法，利用栈来实现算术表达式求值的算法。
• 程序运行时，输入合法的算术表达式（中间值及最终结果要在 0～9 之间，可以包括加减乘除和括号），便可输出相应的计算结果。

说明

• 实验代码还没发，自己写的
• 使用了 C++17 的特性，编译时加上参数 -std=c++17

代码

// #define _DEBUG  // 开启调试
#include <iostream>
#include <optional> // C++17
#include <string>
#include <sstream>
#include <vector>
#include <map>
#include <cmath>
#include <regex>
#include <random>

using std::cin;
using std::cout;
using std::endl;
using std::map;
using std::optional;
using std::ostringstream;
using std::string;
using std::vector;

// Stack template class
// Examples:
//      Stack<int> stack;
//      auto top = stack.GetTop();
//      cout << top.value_or(-1) << endl; // top == -1 if stack is empty
//      stack.Push(100);
//      stack.Push(44);
//      stack.Pop();
//      stack.Push(97);
//      cout << stack.Length() << endl;             // 2
//      if (!stack.IsEmpty())                       // check Stack status before GetTop() manually
//           cout << stack.GetTop().value() << endl; // 97
template <typename ElemType>
class Stack
{
    struct Node
    {
        ElemType data;
        Node *next;
    };

private:
    size_t length_; // 当前栈高
    Node *head_;    // 头结点(无数据)

public:
    Stack();
    ~Stack();
    Stack(const Stack &) = delete;
    Stack &operator=(const Stack &) = delete;

    size_t Length() const { return length_; }
    bool IsEmpty() const { return length_ == 0; }
    bool Push(const ElemType e);
    optional<ElemType> Pop();
    optional<ElemType> GetTop();
};

template <typename ElemType>
Stack<ElemType>::Stack() : length_(0)
{
    head_ = new Node();
    if (!head_)
        throw std::bad_alloc(); // 内存分配失败
    head_->next = nullptr;
}

template <typename ElemType>
Stack<ElemType>::~Stack()
{
    Node *p = head_->next;
    while (p)
    {
        head_->next = p->next;
        // cout << "Deleted: " << p->data << endl;
        delete p;
        p = head_->next;
    }
    delete head_;
}

template <typename ElemType>
bool Stack<ElemType>::Push(const ElemType e)
{
    Node *node = new Node();
    if (!node)
        return false;
    node->data = e; // 前插法
    node->next = head_->next;
    head_->next = node;
    length_++;
    return true;
}

template <typename ElemType>
optional<ElemType> Stack<ElemType>::GetTop()
{
    if (head_->next)
        return head_->next->data;
    return std::nullopt;
}

template <typename ElemType>
optional<ElemType> Stack<ElemType>::Pop()
{
    if (IsEmpty())
        return std::nullopt;
    Node *p = head_->next;
    ElemType e = p->data; // 保存栈顶元素
    head_->next = p->next;
    delete p;
    length_--;
    return e;
}

// ------------ End of Stack ------------------------

class SimpleCalculator
{
private:
    double ans = 0.0;
    map<string, int> op_priority = {
        {"(", 10}, {"random", 7}, {"sqrt", 7}, {"sin", 7}, {"cos", 7}, {"tan", 7},
        {"acos", 7}, {"asin", 7}, {"atan", 7}, {"ln", 7}, {"log", 7}, {"abs", 7},
        {"log", 7}, {"floor", 7}, {"ceil", 7}, {"^", 3}, {"%", 2}, {"*", 2},
        {"/", 2}, {"+", 1}, {"-", 1}, {")", -1}}; // 运算符优先级

public:
    SimpleCalculator() = default;
    SimpleCalculator(const SimpleCalculator &) = delete;
    SimpleCalculator &operator=(const SimpleCalculator &) = delete;

    void Run();
    void ShowHelp() const;
    vector<string> ToSuffixExpr(string &); // 转换为后缀表达式
    vector<string> PreProcess(string &);   // 预处理输入的表达式字符串, 算法界限符与数值分离
    double Evaluate(string &);             // 计算后缀表达式的值
};

void SimpleCalculator::ShowHelp() const
{
    cout << "SimpleCalculator v0.1\n\n"
         << "Supported Operates: \n"
         << "\t+ - * / ^ %\n"
         << "\tsin(N)   cos(N)      tan(N)\n"
         << "\tsin(N)   acos(N)     atan(N)\n"
         << "\tln(N)    logN(M)     random()\n"
         << "\tabs(N)   ceil(N)     floor(N)    sqrt(N)\n"
         << "\nInner constant:\n"
         << "\tpi=3.14159265359\te=2.718281828"
         << endl;
}

vector<string> SimpleCalculator::PreProcess(string &expr)
{
    expr = std::regex_replace(expr, std::regex("\\s+"), "");                             // 删除空格
    expr = std::regex_replace(expr, std::regex("\\bpi"), "3.14159265359");               // 替换 pi
    expr = std::regex_replace(expr, std::regex("\\be"), "2.718281828");                  // 替换 e
    expr = std::regex_replace(expr, std::regex("\\bans"), std::to_string(ans));          // 替换上次计算的结果
    expr = std::regex_replace(expr, std::regex("^-(\\d)"), "0-$1");                      // 负数开头补0
    expr = std::regex_replace(expr, std::regex("(\\D)(-)(\\d)"), "$010$02$03");          // 表达式内部负数前补0
    expr = std::regex_replace(expr, std::regex("([\\-\\+\\*/%\\^\\(\\)]|log)"), " $1 "); // 数值和算符用空格分开, 因为logN(M), log 作为整体,
    std::istringstream iss(expr);
    vector<string> results((std::istream_iterator<string>(iss)), std::istream_iterator<string>()); // 使用空格 split
#ifdef _DEBUG
    cout << "DEBUG: Expression split: ";
    for (auto s : results)
        cout << "[" << s << "] ";
    cout << endl;
#endif
    return results;
}

vector<string> SimpleCalculator::ToSuffixExpr(string &expr)
{
    vector<string> expr_list = PreProcess(expr);
    vector<string> ret;
    Stack<string> op_stack;

    for (string str : expr_list)
    {
        if (isdigit(str[0]))
            ret.push_back(str);
        else if (op_stack.IsEmpty() || op_priority[str] > op_priority[op_stack.GetTop().value()])
            op_stack.Push(str);
        else if (str == ")")
        {
            while (op_stack.GetTop().value() != "(")
                ret.push_back(op_stack.Pop().value());
            op_stack.Pop(); // 丢弃栈中匹配的 (
        }
        else
        {
            while (!op_stack.IsEmpty() && op_stack.GetTop().value() != "(")
                ret.push_back(op_stack.Pop().value());
            op_stack.Push(str);
        }
    }
    while (!op_stack.IsEmpty())
        ret.push_back(op_stack.Pop().value());
#ifdef _DEBUG
    cout << "DEBUG: Suffix Expression: ";
    for (auto s : ret)
        cout << "[" << s << "] ";
    cout << endl;
#endif
    return ret;
}

double SimpleCalculator::Evaluate(string &expr)
{

    vector<string> suffix_expr = ToSuffixExpr(expr);
    Stack<double> stack;
    for (string str : suffix_expr)
    {
        if (isdigit(str[0]))                          // 字符串第一个是数字
            stack.Push(strtod(str.c_str(), nullptr)); // 转化为数字入栈
        else if (str == "abs")
            stack.Push(fabs(stack.Pop().value()));
        else if (str == "sqrt")
            stack.Push(sqrt(stack.Pop().value()));
        else if (str == "sin")
            stack.Push(sin(stack.Pop().value()));
        else if (str == "asin")
            stack.Push(asin(stack.Pop().value()));
        else if (str == "cos")
            stack.Push(cos(stack.Pop().value()));
        else if (str == "acos")
            stack.Push(acos(stack.Pop().value()));
        else if (str == "tan")
            stack.Push(tan(stack.Pop().value()));
        else if (str == "atan")
            stack.Push(atan(stack.Pop().value()));
        else if (str == "ln")
            stack.Push(log(stack.Pop().value()));
        else if (str == "floor")
            stack.Push(floor(stack.Pop().value()));
        else if (str == "ceil")
            stack.Push(ceil(stack.Pop().value()));
        else if (str == "random") // 产生一个 [0, 1) 的随机数
        {
            std::random_device rd; // 随机数生成器
            std::mt19937 mt(rd());
            std::uniform_real_distribution<double> dist(0.0, 1.0);
            stack.Push(dist(mt));
        }

        else // 二元运算符
        {
            double rhs = stack.Pop().value(); // 先出栈的运算符右边的数
            double lhs = stack.Pop().value();
            if (str == "^")
                stack.Push(pow(lhs, rhs));
            else if (str == "log")
                stack.Push(log(rhs) / log(lhs)); // 换底公式求 log_a(b)
            else if (str == "%")
                stack.Push(fmod(lhs, rhs));
            else if (str == "*")
                stack.Push(lhs * rhs);
            else if (str == "/")
                stack.Push(lhs / rhs);
            else if (str == "+")
                stack.Push(lhs + rhs);
            else if (str == "-")
                stack.Push(lhs - rhs);
        }
    }
    return stack.Pop().value(); // 栈顶就是表达式的值
}

void SimpleCalculator::Run()
{
    while (true)
    {
        string input;
        cout << ">>> ";
        getline(cin, input);
        if (input == "help")
        {
            ShowHelp();
            continue;
        }
        try
        {
            double output = Evaluate(input);
            cout << "\nans=" << output << endl
                 << endl;
            ans = output; // 保存运算结果下次使用
        }
        catch (const std::exception &e)
        {
            cout << "表达式有误!" << endl;
        }
    }
}

// --------------------- End of Calculator -------------------------------

int main(int argc, char const *argv[])
{
    SimpleCalculator calculator;
    calculator.Run();
}

功能说明

在实验要求的基础是进行了扩展，添加了一点功能

• 支持浮点数运算
• 支持基本运算加(+)、减(-)、乘(*)、除(/)、取余(%)、乘方(^)运算
• 支持对数运算 ln(N) logN(M)
• 支持三角函数运算 sin(N) cos(N) tan(N)
• 支持反三角函数运算 asin(N) acos(N) atan(N)
• 其它运算
  • 求绝对值 abs(N)
  • 平方根 sqrt(N)
  • 向上取整 ceil(N) 向下取整 floor(N)
  • 产生 [0~1] 的随机数 random()
• 内置常量
  • pi=3.14159265359
  • e=2.718281828
  • ans 保存了上一次的运算结果

运行截图

3.栈的应用-表达式求值

原文：https://www.cnblogs.com/zaxtyson/p/13696153.html