【算法笔记】使用栈(stack)和队列(queue)完成的一个简单计算器(同时求解后缀表达式)

题目描述

读入一个只包含加减乘除的非负整数计算表达式，并求解结果；
本题用来练习栈和队列的使用，核心是中缀表达式转后缀表达式；

输入格式

每次输入一行，整数和运算符之间用一个空格(或者可以不加)分隔；

输出格式

每次输出一行，精确到小数点后 2 位；

输入示例

30 / 90 - 26 + 97 - 5 - 6 - 13 / 88 * 6 + 51 / 29 + 79 * 87 + 57 * 92

输出示例

12178.21

思路

输入的格式为中缀表达式，需要计算结果需要以下两个步骤：

1. 中缀表达式转后缀表达式；
2. 计算后缀表达式；

中缀表达式是人类习惯使用的，但是后缀表达式和前缀表达式更适合计算机的计算过程。中缀表达式可以简单的理解为运算符放在两个操作数中间，但后缀表达式的运算符放在两个操作数之后，前缀即放在两个操作数之前，示例如下：

中缀表达式：3 + 2 * 6 / 3
后缀表达式：3 2 6 * 3 / +
前缀表达式：+ 3 / * 2 6 3

本次程序采用中缀表达式转后缀表达式；

中缀表达式转后缀表达式：

1. 设立一个操作符栈 s ，用于临时存放操作符；设立一个队列 q ，用来存放后缀表达式
2. 从左到右，扫描中缀表达式，每个字符使用包含操作符 op 、操作数 num 和选择项 flag 的结构体表示。此时需要注意两点：① 操作数可能不止一位，不能只关心个位数；② 操作前需要把中缀表达式中的空格全部删除；
3. 如果碰到操作数，就将操作数加入后缀表达式 q 的 num 中，并把 flag 设为 true；如果碰到操作符(记为 op)，就比较 op 与栈顶操作符 s.top() 的优先级，优先级排序为乘法 == 除法 > 加法 == 减法；
4. op 与 s.top() 优先级的比较规则如下：若 op 优先级大于 s.top()，将 op 压入 s；若 op 优先级小于 s.top()，将 s 栈顶弹出到后缀表达式 q 中，直到 op 的优先级大于 s.top() 或者 s 为空；
5. 重复上述操作 3 和 4，直到中缀表达式扫描完毕，若 s 中仍有元素，将其依次弹出至 q 中；

计算后缀表达式

• 从左到右扫描后缀表达式，如果是操作数(flag == true)，就压入栈 s，如果是操作符(flag == false)，就连续弹出两个操作数 temp2 和 temp1，但需要注意，先弹出的是 temp2，后弹出的是 temp1；
• 将 temp1 和 temp2 与操作符运算，将计算结果重新压入栈 s，此时需要注意，操作结果需要用 double 型变量，因为除法操作可能出现非整除；
• 最后，栈 s 中仅剩一个数，这个数就是计算结果；

代码

#include <iostream>
#include <stdio.h>
#include <string>
#include <queue>
#include <stack>
#include <map>
using namespace std;

struct node{
	double num; //操作数
	char op; //操作符
	bool flag; //选择操作数or操作符
};

string str; //存放中缀表达式的字符串
stack<node> s; //存放操作符的栈
queue<node> q; //存放后缀表达式
map<char, int> op; // 定义操作符的优先级，加减为1，乘除为2

void abbr(){ //删除空格
	for(string::iterator it=str.begin();it!=str.end();it++){
		if(*it == ' ') str.erase(it);
	}
}

void change(){ //中缀表达式转后缀表达式
	node temp; 
	for(int i=0;i<str.length();){ // 逐一扫描中缀表达式
		if(str[i]>='0' && str[i]<='9'){
			temp.flag = true; // 如果是数字，flag=true
			temp.num = str[i++] - '0'; //读取个位数字
			while(i<str.length() && str[i]>='0' && str[i]<='9'){
				temp.num = temp.num * 10 + (str[i++] - '0');
			} //判断是否有高位数字，并读取
			q.push(temp); //将元素(操作数)压入队列
		}
		else{
			temp.flag = false; // 如果是操作符，flag=false
			while(!s.empty() && op[str[i]]<=op[s.top().op]){
				q.push(s.top());
				s.pop();
			} //如果新操作符优先级小于等于栈顶，将栈顶操作符压入队列中
			temp.op = str[i];
			s.push(temp);
			//上述操作执行后，压入栈的操作符优先级最高，或着是栈中唯一元素
			i++;
		}
	}
	while(!s.empty()){ //所有操作数入队列后，将栈中剩余操作符压入队列
		q.push(s.top());
		s.pop();
	}
}

void formula(queue<node> q){ //用于打印后缀表达式，输入为change()操作后的队列
	int n = q.size();
	printf("Postfix expression:\n");
	while(!q.empty()){
		if(q.front().flag == true){
			printf("%.0f ", q.front().num);
		}
		else{
			printf("%c ", q.front().op);
		}
		q.pop();
	}
	printf("\n");
}

double cal(){
	double temp1, temp2;
	node cur, temp;
	while(!q.empty()){
		cur = q.front(); //记录队列首元素
		q.pop();
		if(cur.flag == true) s.push(cur); //如果是操作数，压入栈中
		else{ //如果是操作符
			temp2 = s.top().num; //先弹出第二个操作数
			s.pop();
			temp1 = s.top().num; //后弹出第一个
			s.pop();
			temp.flag = true; // 临时的node表示操作数，使用node是为了计算后，将临时数值结果压入栈中
			if(cur.op == '+') temp.num = temp1 + temp2;
			else if(cur.op == '-') temp.num = temp1 - temp2;
			else if(cur.op == '*') temp.num = temp1 * temp2;
			else temp.num = temp1 / temp2;//定义加减乘除操作
			s.push(temp); //将临时结果压入栈中
		}
	}
	return s.top().num; //返回栈中仅有的元素，即最终结果
}

int main(){
	// 定义运算符的优先级
	op['+'] = op['-'] = 1;
	op['*'] = op['/'] = 2;
	while(!s.empty()) s.pop();
	getline(cin, str); //输入中缀表达式
	abbr(); //删除空格
	change(); //转为后缀表达式
	formula(q); // 显示后缀表达式
	printf("result = %.2lf\n", cal());// 显示最终结果，并保留两位小数
}

示例

输入为

1 + 3 * 5 / 4 * 8 / 9 * 6 * 2 / 3 / 7 + 3 * 8 / 2

输出为

Postfix expression:
1 3 5 * 4 / 8 * 9 / 6 * 2 * 3 / 7 / + 3 8 * 2 / + 
result = 14.90

转载：https://blog.csdn.net/weixin_41788963/article/details/104378772