栈的应用——制作计算器

目标和要求

目标：
设计并实现一个整型算术表达式计算器。
要求：

1. 只处理整型算术运算表达式，即运算符至少包含±*/()
2. 要求抽象出链栈结构进行独立实现。
3. 存储结构采用链式存储，基于链栈完成计算器功能。。

原理

为解决这个问题，我们需要用两个栈，一个操作数栈栈存储数据，一个运算符栈存储符号，然后根据优先级来进行运算。
流程如下：

1. 如果是数字，压进操作数栈中；
2. 如果是“+，-”，则观察运算符栈中是否有相同级或更高级的运算符，即“+，-，*，/”，如果有，先运算栈里面的，再把现在这个压进运算符栈中。
3. 如果是“，/”，则观察运算符栈中是否有相同级或更高级的运算符，即“，/”，如果有，先运算栈里面的，再把现在这个压进运算符栈中。
4. 如果是”（“，则直接放进运算符栈中。
5. 如果是”）“，则一直处理运算符中的符号，直到遇到”（“。

下面我们会对过程进行一个模拟：

分析和实现

多话不说，直接上代码吧，相关感觉比较重要的地方都做了标注，相信聪明的你一定可以看的明白。

#include <string>
template<typename T>
class Stack
{
public:
	Stack();
	~Stack();
	bool empty() const;
	T get_top();
	void push(T x);
	void pop();
private:
	struct node
	{
		T data;
		node* next;
	};
	int count;
	node* top;
};


template<typename T>
Stack<T>::Stack()
{
	count = 0;
	top = NULL;
}

template<typename T>
bool Stack<T>::empty() const
{
	return count == 0;
}

template<typename T>
T Stack<T>::get_top()
{
	if (!empty())	
		return top->data;
}

template<typename T>
void Stack<T>::push(T x)
{
	node* s = new node;
	s->data = x;
	s->next = top;
	top = s;
	count++;
}

template<typename T>
void Stack<T>::pop()
{
	if (!empty())
	{
		node* n = top;
		top = n->next;
		delete n;
		count--;
	}	
}

template<typename T>
Stack<T>::~Stack()
{
	while (!empty())
		pop();
}

#include <iostream>
#include <vector>
using namespace std;
vector<string> split(const string& expression);
int evaluateExpression(const string& expression);
void processAnOperator(Stack<int>& operandStack, Stack<char>& operatorStack);

int main()
{
	cout << "Enter the expression you need to calculate:  ";
	string expression;
	getline(cin, expression);
	cout << evaluateExpression(expression) << endl;
	return 0;
}

//将表达式的数字和字符按顺序放到数组中隔开
vector<string> split(const string& expression)
{
	vector<string> v;//将数字和符号分开分别放入不同的字符串数组里
	string numberString;//存放数的字符串
	for (unsigned i = 0; i < expression.length(); i++)
	{
		if (isdigit(expression[i]))//判断是不是阿拉伯数字
			numberString.append(1, expression[i]);//将一个expression[i]加到numberString里面
		else
		{
			if (numberString.size() > 0)
			{
				v.push_back(numberString);
				numberString.erase();
			}
			if (!isspace(expression[i]))//判断是否为空格或换行
			{
				string s;
				s.append(1, expression[i]);
				v.push_back(s);
			}
		}
	}
	if (numberString.size() > 0)
		v.push_back(numberString);
	return v;
}

//将数字和符号按规则放到不同的栈并调用函数来运算。
int evaluateExpression(const string& expression)
{
	Stack<int> operandStack;
	Stack<char> operatorStack;
	vector<string> tokens = split(expression);

	for (unsigned i = 0; i < tokens.size(); i++)
	{
		if (tokens[i][0] == '+' || tokens[i][0] == '-')
		{
			while (!operatorStack.empty() && (operatorStack.get_top() == '+' || operatorStack.get_top() == '-' || operatorStack.get_top() == '*' || operatorStack.get_top() == '/'))
			{
				processAnOperator(operandStack, operatorStack);
			}
			operatorStack.push(tokens[i][0]);
		}
		else if (tokens[i][0] == '*' || tokens[i][0] == '/')
		{	
			while (!operatorStack.empty() && (operatorStack.get_top() == '*' || operatorStack.get_top() == '/'))
			{
				processAnOperator(operandStack, operatorStack);
			}
			operatorStack.push(tokens[i][0]);
		}
		else if (tokens[i][0] == '(')
			operatorStack.push(tokens[i][0]);
		else if (tokens[i][0] == ')')
		{
			while (operatorStack.get_top() != '(')
			{
				processAnOperator(operandStack, operatorStack);
			}
			operatorStack.pop();
		}
		else
			operandStack.push(atoi(tokens[i].c_str()));
	}
	while (!operatorStack.empty())
	{
		processAnOperator(operandStack, operatorStack);
	}
	return operandStack.get_top();
}

//运算函数
void processAnOperator(Stack<int>& operandStack, Stack<char>& operatorStack)
{
	char op = operatorStack.get_top();
	operatorStack.pop();
	int op1 = operandStack.get_top();
	operandStack.pop();
	int op2 = operandStack.get_top();
	operandStack.pop();
	if (op == '+')  operandStack.push(op2 + op1); 
	else if (op == '-')  operandStack.push(op2 - op1); 
	else if (op == '*')  operandStack.push(op2 * op1); 
	else if (op == '/')  operandStack.push(op2 / op1); 
}
var foo = 'bar';

运行结果

ps
我在另一篇文章写了一个栈的相关知识，有兴趣的同学可以去参考一下。链接我放在下面：
链接: 栈的探究——顺序栈和链栈.

如果对您有所帮助的话，不妨点个赞支持一下呗！