[数据结构与算法]万能计算器——中缀表达式转换成后缀表达式（C++实现）【可以计算小数和负数】

核心代码与思路：

int GetExprValue(vector<string> srcVec)   //根据后缀表达式求值
{
	stack<int> temp;
	char op = '\0';
	int a = 0;
	int b = 0;
	for (int i = 0; i < srcVec.size(); i++) {
		op = srcVec[i][srcVec[i].length() - 1];
		if (isdigit(op)) {
			temp.push(atoi(srcVec[i].c_str())); //如果是数字则直接入栈
		} else {
			a = temp.top();                     //否则从栈中取出两个操作数进行计算（注意操作数的左右顺序）
			temp.pop();							//然后将计算的值入栈
			b = temp.top();
			temp.pop();
			temp.push(CalFunc(b, op, a));
		}
	}
	return temp.top();
}

vector<string> GetSufix(string src)
{
	vector<string> dest;
	stack<char> opStack;
	int i = 0;
	string temp = "";
	while (i < src.length()) {
		if (isdigit(src[i])) {  //如果遇到数字就读取一个操作数加入后缀表达式中，注意是引用传递
			dest.push_back(ReadIntNum(src, i));
			i--; //由于后面会进行++操作，这里要保持在读到的最后一个数字位上
		} else if (IsLeftBrac(src[i])) { //如果遇到左括号直接入栈
			opStack.push(src[i]);
		} else if (IsRightBrac(src[i])) { //如果遇到右括号将栈顶元素出栈，加入后缀表达式，直到遇到左括号，将这个左括号弹出
			while (opStack.top()!= MatchBrac(src[i])) {
				temp += opStack.top();
				dest.push_back(temp);
				opStack.pop();
				temp = "";
			}
			opStack.pop(); //弹出( [ {
		} else if (IsOprand(src, i)){  //如果遇到的是操作符，将站定优先级大于等于该操作符的元素出栈，加入后缀表达式
			while ((!opStack.empty()) && (GetPri(opStack.top()) >= GetPri(src[i])) &&
					!IsLeftBrac(opStack.top())) {  //直到遇到左括号或栈为空（为空的判断优先）
				temp += opStack.top();
				dest.push_back(temp);
				opStack.pop();
				temp = "";
				
			}
			opStack.push(src[i]); //将当前字符入栈
		}
		
		i++;
	}
	while (!opStack.empty()) {
		temp += opStack.top();
		dest.push_back(temp);
		opStack.pop();
		temp = "";
	}

	return dest;
}

完整代码：

#include <iostream>
#include <vector>
#include <stack>
#include <cctype>
#include <cstdlib>
using namespace std;

bool IsLeftBrac(char ch)
{
	return (ch == '(' || ch == '[' || ch == '{');
}

bool IsRightBrac(char ch)
{
	return (ch == ')' || ch == ']' || ch == '}');
}

char MatchBrac(char ch)
{
	char temp;
	switch (ch) {
		case ')':
			temp = '(';
			break;
		case ']':
			temp = '[';
			break;
		case '}':
			temp = '{';
			break;
		default:
			temp = '\0';
			break;	
	}
	return temp;
}

bool IsOprand(string src, int idx)
{
	bool isSign = (src[idx] == '+' || src[idx] == '-' || src[idx] == '*' || src[idx] == '/');
	bool isValid = isdigit(src[idx - 1]) || IsRightBrac(src[idx - 1]); //运算符的左侧只能是数字或者右括号
	return (isSign && isValid);
}

string ReadIntNum(string src, int &idx)
{
	string value = "";
	if (src[idx - 1] == '-' && !IsOprand(src, idx - 1)){ //当数字的前一个是'-'且这个'-'不能作为运算符时就作为负号使用
			 value += '-';
	}
	while (isdigit(src[idx])) {
		value += src[idx++];
	}
	return value;
	
}

int CalFunc(int a, char op, int b)
{
	int ret = 0;
	switch (op) {
		case '+':
			ret = a + b;
			break;
		case '-':
			ret = a - b;
			break;
		case '*':
			ret = a * b;
			break;
		case '/':
			ret = a / b;
			break;
		default:
			ret = 0;
			break;
	}
	return ret;
}

int GetPri(char ch)
{
	int pri = 0;
	switch (ch) {
		case '+':
		case '-':
			pri = 1;
			break;
		case '*':
		case '/':
			pri = 2;
			break;
		default:
			pri = 0;
			break;
	}
	return pri;
}

int GetExprValue(vector<string> srcVec)   //根据后缀表达式求值
{
	stack<int> temp;
	char op = '\0';
	int a = 0;
	int b = 0;
	for (int i = 0; i < srcVec.size(); i++) {
		op = srcVec[i][srcVec[i].length() - 1];
		if (isdigit(op)) {
			temp.push(atoi(srcVec[i].c_str())); //如果是数字则直接入栈
		} else {
			a = temp.top();                     //否则从栈中取出两个操作数进行计算（注意操作数的左右顺序）
			temp.pop();							//然后将计算的值入栈
			b = temp.top();
			temp.pop();
			temp.push(CalFunc(b, op, a));
		}
	}
	return temp.top();
}

vector<string> GetSufix(string src)
{
	vector<string> dest;
	stack<char> opStack;
	int i = 0;
	string temp = "";
	while (i < src.length()) {
		if (isdigit(src[i])) {  //如果遇到数字就读取一个操作数加入后缀表达式中，注意是引用传递
			dest.push_back(ReadIntNum(src, i));
			i--; //由于后面会进行++操作，这里要保持在读到的最后一个数字位上
		} else if (IsLeftBrac(src[i])) { //如果遇到左括号直接入栈
			opStack.push(src[i]);
		} else if (IsRightBrac(src[i])) { //如果遇到右括号将栈顶元素出栈，加入后缀表达式，直到遇到左括号，将这个左括号弹出
			while (opStack.top()!= MatchBrac(src[i])) {
				temp += opStack.top();
				dest.push_back(temp);
				opStack.pop();
				temp = "";
			}
			opStack.pop(); //弹出( [ {
		} else if (IsOprand(src, i)){  //如果遇到的是操作符，将站定优先级大于等于该操作符的元素出栈，加入后缀表达式
			while ((!opStack.empty()) && (GetPri(opStack.top()) >= GetPri(src[i])) &&
					!IsLeftBrac(opStack.top())) {  //直到遇到左括号或栈为空（为空的判断优先）
				temp += opStack.top();
				dest.push_back(temp);
				opStack.pop();
				temp = "";
				
			}
			opStack.push(src[i]); //将当前字符入栈
		}
		
		i++;
	}
	while (!opStack.empty()) {
		temp += opStack.top();
		dest.push_back(temp);
		opStack.pop();
		temp = "";
	}

	return dest;
}

int main()
{
	string src;
	while (cin >> src) {
		vector<string> ret = GetSufix(src);
		cout << GetExprValue(ret) << endl;
	}
	return 0;
}

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖