4.2 实现基于栈的表达式求值计算器(难度4/10)

本作业主要考察：解释器模式的实现思想/栈结构在表达式求值方面的绝对优势

C++数据结构与算法夯实基础作业列表

通过栈的应用，理解特定领域设计的关键作用，给大家眼前一亮的感觉。深刻理解计算机语言和人类语言完美结合的杰作。是作业中的上等作品，是数据结构与算法的典型代表。

这个作业是我最心爱的一个。因为我有个盗版Win10居然打不开计算器；还有就是一些高级比如指数运算怕不会操作Windows的自带计算器算错，要用自己的计算器再验证一遍；第三个就是Windows的计算器不支持回车键和命令行，我的就可以，回车一下就行，Windows的总是要鼠标点来点去，烦不胜烦。

需求如下：

实现表达式求值的计算器，以支持加、减、乘、除、指数幂、括号，6种操作。

实现代码完成下面的测试用例，要求和预期输出结果一致

接口提示（可以自行定义接口，只要实现合理，能实现需求就行）：

Stackitem.h

#pragma once
 
#include  //ostream
using namespace std;
 
template<typename T> class CStack;
 
template<typename T>
class CStackitem
{
public:
	friend class CStack;
 
	CStackitem(void);
	CStackitem(T _data);
	CStackitem(const CStackitem& _item);
	~CStackitem(void);
 
	const T GetData(void) const;
 
private:
	CStackitem& operator=(const CStackitem& _item);//disallow a = b;
 
private:
	CStackitem* pPre;
	CStackitem* pNext;
	T data;
};

Stack.h

#pragma once
 
#include "Stackitem.h"
 
template<typename T>
class CStack
{
public:
	CStack(void);
	CStack(const CStack& _stack);
	~CStack(void);
 
public:
	const T& top(void) const;
	bool empty(void) const;
	size_t size(void) const;
	void push(const CStackitem& _item);
	const T pop(void);
 
private:
	CStack& operator=(const CStack& _stack);//a = b; is not allowed
 
private:
 
	CStackitem* m_pTail;
	size_t m_size;
};

Calculator.h

#pragma once
 
#include 
#include 
#include 
#include 
using namespace std;
 
#include "ExpressionException.h"
 
typedef list Expression;
 
ostream& operator<<(ostream& _os, const Expression& _item);
 
class Calculator
{
public:
	Calculator(const char* _infix);
	Calculator(const string& _infix);
	~Calculator(void);
	
public:
	string GetExpression(void) const;
	void SetExpression(const string& _expression);
	
	template<typename T>
	T GetValue(void ) const;
 
	Expression ToPostfix(void) const;
 
public:
	static Expression ToPostfix(const string& pre);
	static bool Check(const string& _expression, string& _invalidInfor);
 
private:
	static void ToPostfix(const string& pre, Expression& post);
	static bool IsOperator(char op);                         // 判断是否为运算符 
	static int Priority(char op);                            // 求运算符优先级 
	static void ReadSpace(string::const_iterator& _itr, string::const_iterator& _end);
	static void ReadNumber(string::const_iterator& itr, string::const_iterator& _end, string& _value);
	
private:
	string m_infix;
};

main.cpp

#include 
#include 
#include 
#include 
using namespace std;
 
#include "Stack.h"
#include "Calculator.h"
 
void InputAndCalculator(list& listCalculator);
void Output(const list& listCalculator);
void TestAll(list& listCalculator);
 
int main(int argc, char** argv)
{
	cout<<"support: + - * / ^ ( )"<
	cout<<"Input 0 for end your input."<
 
	list listCalculator;
 
	InputAndCalculator(listCalculator);//Extra credit 1:(1)any space (2)catch invalid input
	
	return 0;
}
void InputAndCalculator(list& listCalculator)
{
	while (true)
	{
		string sLine, invalidInfor;
		getline(cin, sLine);
		if (Calculator::Check(sLine, invalidInfor) == false)//Extra credit 1:(1)any space (2)catch invalid input
		{
			cout<
			continue;
		}
		listCalculator.push_back(sLine);
		Output(listCalculator);
		listCalculator.clear();
	}
}

参考答案：

C++表达式求值（Stack and Expression）​

blog.csdn.net/calmreason/article/details/78163268​编辑