[保研/考研机试] KY102 计算表达式上海交通大学复试上机题 C++实现

描述

对于一个不存在括号的表达式进行计算

输入描述：

存在多组数据，每组数据一行，表达式不存在空格

输出描述：

输出结果

示例1

输入：

6/2+3+3*4

输出：

思路：

①设立运算符和运算数两个栈，,一个用来存储运算符，另一个用来存储运算数。

②在运算符栈中放置一个特殊运算符#,其优先级最低。

③将表达式尾部添加一个特殊运算符$,其优先级次低。

④从左至右依次遍历字符串，若遍历到运算符，则将其与运算符栈的栈顶元素进行比较，若运算符栈的栈顶的优先级小于该运算符，则将该运算符压入运算符栈；若运算符栈的栈顶的优先级大于该运算符，则弹出该栈顶运算符，从运算数栈中依次弹出运算数，完成弹出运算符对应的运算后，再将该结果压入运算数栈。

⑤若遍历到表达式中的运算数，则直接压入运算数栈。

⑥若运算符栈中仅剩两个特殊运算符#和$,则表达式运算结束，此时运算数栈中唯一的数字就是表达式的值。

源代码：

#include<iostream>
#include<stack>
#include<map>
#include<string>
using namespace std;

//习题5.2 KY102 计算表达式
//考虑到需要计算的数字可能不止一位，就从检测到数字的索引开始，一直到检测不到数字的索引，这之间的就是一整个数字
double getNum(string str, int& index) {
	double res = 0;
	while (isdigit(str[index])) {
		res = res * 10 + str[index] - '0';
		index++;
	}
	return res;
}

double cal(double x, double y, char op) {
	double res = 0;
	if (op == '+') {
		res = x + y;
	}
	else if (op == '-') {
		res = x - y;
	}
	else if (op == '*') {
		res = x * y;
	}
	else if (op == '/') {
		res = x / y;
	}
	return res;
}

int main()
{
	string s;
	//存储多个运算符号的优先级
	map<char, int> maps = { {'#',0},{'$',1},{'+',2},{'-',2},{'*',3},{'/',3} };
	while (cin >> s) {
		stack<char> symbol;
		stack<double> number;
		//在运算符栈中放置一个特殊运算符#,其优先级最低。
		symbol.push('#');
		//将表达式尾部添加一个特殊运算符$,其优先级次低
		s = s + '$';
		int index = 0;
		while (index < s.size()) {
			if (isdigit(s[index])) { //遍历到数字
				number.push(getNum(s, index));
			}
			else { //遍历到运算符
				//若运算符栈的栈顶的优先级小于该运算符，则将该运算符压入运算符栈
				if (maps[s[index]] > maps[symbol.top()]) {
					symbol.push(s[index]);
					index++;
				}
				//否则，弹出该栈顶运算符，从运算数栈中依次弹出运算数，完成弹出运算符对应的运算后，再将该结果压入运算数栈
				else {
					double x = number.top();
					number.pop();
					double y = number.top();
					number.pop();
					number.push(cal(y, x, symbol.top()));
					symbol.pop();
				}
			}
		}
		printf("%.0f", number.top());
	}

	return 0;
}