#include
#include
#include
#include
#include
using namespace std;
// 定义操作符的优先级
int getPriority(char op) {
switch(op) {
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
case '^':
return 3;
default:
return 0;
}
}
// 计算表达式
double calculate(double num1, double num2, char op) {
switch(op) {
case '+':
return num1 + num2;
case '-':
return num1 - num2;
case '*':
return num1 * num2;
case '/':
return num1 / num2;
case '^':
return pow(num1, num2);
default:
return 0;
}
}
// 中缀表达式转后缀表达式
vector infixToPostfix(string& infix) {
vector postfix; // 后缀表达式
vector opStack; // 操作符栈
istringstream iss(infix); // 将字符串转为流
string token;
while(iss >> token) { // 读取每个token
char c = token[0];
if(isdigit(c)) { // 如果是数字，直接加入后缀表达式
postfix.push_back(token);
} else if(c == '(') { // 如果是左括号，压入操作符栈
opStack.push_back(c);
} else if(c == ')') { // 如果是右括号，弹出操作符栈直到遇到左括号
while(opStack.back() != '(') {
postfix.push_back(string(1, opStack.back()));
opStack.pop_back();
}
opStack.pop_back(); // 弹出左括号
} else { // 如果是操作符
while(!opStack.empty() && opStack.back() != '(' && getPriority(opStack.back()) >= getPriority(c)) {
// 弹出操作符栈中优先级高于或等于当前操作符的所有操作符，并加入后缀表达式
postfix.push_back(string(1, opStack.back()));
opStack.pop_back();
}
opStack.push_back(c); // 将当前操作符压入操作符栈
}
}
while(!opStack.empty()) { // 将操作符栈中的操作符加入后缀表达式
postfix.push_back(string(1, opStack.back()));
opStack.pop_back();
}
return postfix;
}
// 计算后缀表达式
double evaluatePostfix(vector& postfix) {
vector numStack; // 数字栈
for(string token : postfix) { // 遍历后缀表达式中的每个token
char c = token[0];
if(isdigit(c)) { // 如果是数字，将其转换为double类型并压入数字栈
numStack.push_back(stod(token));
} else { // 如果是操作符，弹出数字栈中的两个数字进行计算，并将计算结果压入数字栈
double num2 = numStack.back();
numStack.pop_back();
double num1 = numStack.back();
numStack.pop_back();
double result = calculate(num1, num2, c);
numStack.push_back(result);
}
}
return numStack.back(); // 最终数字栈中的唯一元素即为表达式的结果
}
int main() {
string infix = "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3"; // 中缀表达式
vector postfix = infixToPostfix(infix); // 将中缀表达式转为后缀表达式
double result = evaluatePostfix(postfix); // 计算后缀表达式
cout << result << endl;
return 0;
}
