欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

栈的应用——制作计算器

程序员文章站 2022-05-25 07:55:48
...

栈的应用——制作计算器

目标和要求

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

  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
我在另一篇文章写了一个栈的相关知识,有兴趣的同学可以去参考一下。链接我放在下面:
链接: 栈的探究——顺序栈和链栈.

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