P10473 表达式计算4

屈老师

表达式计算4

题目描述

给出一个表达式，其中运算符仅包含 +，-，*，/，^{，要求求出表达式的最终值。}

数据可能会出现括号情况，还有可能出现多余括号情况。

数据保证不会出现超过 int 范围的数据，数据可能会出现负数情况。

输入格式

仅一行一个字符串，即为表达式。

输出格式

仅一行，既为表达式算出的结果。

样例 #1

样例输入 #1

(2+2)^(1+1)

样例输出 #1

提示

表达式总长度不超过 $30$。

#include <iostream>
#include <cmath>
#include <stack>
#include <string>
#include <cctype>  // 用于 isdigit 函数
#include <sstream> // 用于处理多位数字
#define int long long
using namespace std;

// 定义操作符的优先级
int precedence(char op) {
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/') return 2;
    if (op == '^') return 3;
    return 0;
}

// 中缀转后缀表达式
string infixToPostfix(const string& expr) {
    stack<char> operators;
    string postfix = "";
    for (size_t i = 0; i < expr.size(); ++i) {
        char ch = expr[i];
        if (isdigit(ch)) {
            // 处理多位数字
            while (i < expr.size() && isdigit(expr[i])) {
                postfix += expr[i];
                i++;
            }
            postfix += ' '; // 用空格分隔数字
            i--; // 回退一位
        }
        else if (ch == '(') {
            operators.push(ch);
        }
        else if (ch == ')') {
            while (!operators.empty() && operators.top() != '(') {
                postfix += operators.top();
                postfix += ' ';
                operators.pop();
            }
            operators.pop(); // 弹出左括号
        }
        else if (ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '^') {
            while (!operators.empty() && precedence(operators.top()) >= precedence(ch)) {
                postfix += operators.top();
                postfix += ' ';
                operators.pop();
            }
            operators.push(ch);
        }
    }
    // 弹出栈中剩余的运算符
    while (!operators.empty()) {
        postfix += operators.top();
        postfix += ' ';
        operators.pop();
    }
    return postfix;
}

// 计算后缀表达式的值
int evaluatePostfix(const string& postfix) {
    stack<int> operands;
    istringstream iss(postfix);
    string token;
    while (iss >> token) {
        if (isdigit(token[0])) {
            operands.push(stoi(token)); // 将字符串转换为整数并入栈
        }
        else {
            int b = operands.top(); operands.pop();
            int a = operands.top(); operands.pop();
            if (token[0] == '+') operands.push(a + b);
            else if (token[0] == '-') operands.push(a - b);
            else if (token[0] == '*') operands.push(a * b);
            else if (token[0] == '/') operands.push(a / b);
            else if (token[0] == '^') operands.push(pow(a, b));
        }
    }
    return operands.top();
}

signed main() {
    string expr;
    getline(cin, expr);

    string postfix = infixToPostfix(expr);
    int result = evaluatePostfix(postfix);

    cout << result << endl;
    return 0;
}