数据结构实验3：算术表达式求值

一、问题描述

简单的算术表达式中可能出现运算数、运算符、圆括号()，从键盘输入一个表达式，实现表达式的求值，并输出结果。

例子：22+15*(33-27)/3的值为52

二、实验目的

掌握栈的存储与操作。

三、实验内容及要求

1、构造栈的数据结构。
2、实现栈的创建、查找、遍历、输出、入栈、出栈等基本操作。

• main.cpp：

#include <iostream>
#include <string>

using namespace std;

// 前置声明，用于实现递归
int evaluate(string::iterator& it, string::iterator end);

// 解析因子（数字或括号内的表达式）
int evaluateFactor(string::iterator& it, string::iterator end)
{
    int factor = 0;
    // 判断是否是括号内的表达式
    if (it != end && *it == '(')
    {
        ++it; // 跳过 '('
        factor = evaluate(it, end);
        if (it != end)
        {
            ++it; // 跳过 ')'
        }
    }
    else
    {
        // 解析数字
        while (it != end && isdigit(*it))
        {
            factor = factor * 10 + (*it - '0');
            ++it;
        }
    }
    return factor;
}

// 解析项（由乘法和除法组成）
int evaluateTerm(string::iterator& it, string::iterator end)
{
    int term = evaluateFactor(it, end);
    // 循环处理乘法和除法
    while (it != end && (*it == '*' || *it == '/'))
    {
        char op = *it;
        ++it; // 跳过运算符
        int factor = evaluateFactor(it, end);
        if (op == '*')
        {
            term *= factor;
        }
        else
        {
            term /= factor;
        }
    }
    return term;
}

// 解析完整表达式（由加法和减法组成）
int evaluate(string::iterator& it, string::iterator end)
{
    int expressionValue = evaluateTerm(it, end);
    // 循环处理加法和减法
    while (it != end && (*it == '+' || *it == '-'))
    {
        char op = *it;
        ++it; // 跳过运算符
        int term = evaluateTerm(it, end);
        if (op == '+')
        {
            expressionValue += term;
        }
        else
        {
            expressionValue -= term;
        }
    }
    return expressionValue;
}

int main()
{
    // string expression = "22+15*(33-27)/3";
    string expression = "10+2*(6/2)";
    string::iterator it = expression.begin();
    // 输出计算结果
    cout << evaluate(it, expression.end()) << endl;

    return 0;
}

• stack.h：

#pragma once
#include<vector>

namespace chen
{
	template<class T, class Container = std::vector<T>>
	class stack
	{
	public:
		void push(const T& x)
		{
			_con.push_back(x);
		}

		void pop()
		{
			_con.pop_back();
		}

		const T& top()
		{
			return _con.back();
		}

		bool empty()
		{
			return _con.empty();
		}

		size_t size()
		{
			return _con.size();
		}

	private:
		Container _con;
	};
}

四、数据结构设计及算法原理

数据结构定义

在这个问题中，我们主要使用了C++的标准库中的string和iterator。字符串用于存储输入的算术表达式，迭代器用于在解析过程中跟踪当前位置。

变量定义

• it：这是一个迭代器，用于跟踪当前解析到了算术表达式的哪个位置。
• end：这是另一个迭代器，指向字符串的末尾，用于避免迭代器越界。
• expressionValue, term, factor：这些是整数变量，用于存储中间计算结果。

运算过程或流程图

1. 从表达式的左侧开始，用迭代器it标识当前位置。
2. 调用evaluate函数开始解析整个表达式。
   • 在evaluate内部，通过调用evaluateTerm来解析由乘法和除法组成的项。
   • evaluateTerm通过调用evaluateFactor来解析单独的因子。
   • 递归地解析括号内的子表达式。
3. 对于每个操作符（+、-、*、/），分别执行相应的计算。
4. 返回计算的结果。

五、测试数据及结果分析

测试数据 1

• 输入：22+15*(33-27)/3
• 输出：52
  

分析：这是一个包含加法、减法、乘法和除法的复杂表达式。程序成功地计算了表达式并返回了正确的结果。

测试数据 2

• 输入：10+2*(6/2)
• 输出：16
  

分析：这个表达式主要用于测试程序是否能正确处理括号和除法。结果显示程序能准确计算。

六、总结与思考

在解决这个问题的过程中，我认识到递归在解析表达式这类问题上的强大能力。递归能自然地处理嵌套结构，如括号内的子表达式。

同时，通过使用迭代器和对其进行精确控制，我们能避免很多常见的错误，比如数组越界。不过，迭代器的使用也要非常小心，以避免越界或者无效解引用。

这个项目也让我更加理解如何将一个大问题分解为更小的、更易于管理的子问题。具体来说，通过将表达式拆分为项和因子，再逐一解析和计算，整个问题变得更容易解决。