MT3034 算术招亲

简介: MT3034 算术招亲

115781ef918a4dc2b420cc38f61f29ac.jpg

4d4ae993fdab49a58ff839619c2751b0.jpg

跟MT3033新的表达式类似,只多了一个括号合法性的判断

#include <bits/stdc++.h>
using namespace std;
const int N = 40;
bool tag[N];
bool is_op(char c)
{
    return c == '+' || c == '-' || c == '*' || c == '/' || c == '^';
}
int priority(char op)
{ // 优先级排序
    if (op == '+' || op == '-')
        return 1;
    if (op == '*' || op == '/')
        return 2;
    if (op == '^')
        return 3;
    return -1;
}
void process_op(stack<int> &st, char op)
{
    int r = st.top();
    st.pop();
    int l = st.top();
    st.pop();
    switch (op)
    {
    case '+':
        st.push(l + r);
        break;
    case '-':
        st.push(l - r);
        break;
    case '*':
        st.push(l * r);
        break;
    case '/':
        st.push(l / r);
        break;
    case '^':
        st.push(pow(l, r));
        break;
    }
}
 
int evaluate(string &s)
{
    stack<int> st;
    stack<char> op;
    for (int i = 0; i < s.size(); i++)
    {
        if (s[i] == '(')
        {
            if (!tag[i])
            {
                continue; // 括号位置不合法
            }
            op.push(s[i]);
        }
        else if (s[i] == ')')
        {
            if (!tag[i])
            {
                continue; // 括号位置不合法
            }
            while (op.top() != '(')
            {
                process_op(st, op.top());
                op.pop();
            }
            op.pop();
        }
        else if (is_op(s[i]))
        { // 运算符优先级
            while (!op.empty() && priority(op.top()) >= priority(s[i]))
            {
                process_op(st, op.top());
                op.pop();
            }
            op.push(s[i]);
        }
        else
        {
            int num = 0;
            while (i < s.size() && isdigit(s[i]))
            {
                num = num * 10 + s[i] - '0';
                i++;
            }
            i--;
            st.push(num);
        }
    }
    while (!op.empty())
    {
        process_op(st, op.top());
        op.pop();
    }
    return st.top();
}
 
void init(string &s)
{ // 去除多余的括号
    stack<pair<char, int>> st;
    for (int i = 0; i < s.size(); i++)
    {
        if (!st.empty() && st.top().first == '(' && s[i] == ')')
        {                                         // 如果栈顶为(并且当前遍历到了(  --> 合法
            tag[i] = tag[st.top().second] = true; // 两个位置为true 即括号位置合法
            st.pop();                             // 合法的(弹出
        }
        else if (s[i] == '(') // 记录(位置
        {
            st.push({'(', i});
        }
    }
}
 
int main()
{
    string s;
    cin >> s;
    init(s);
    cout << evaluate(s);
    return 0;
}


相关文章
Qt浮点数(float)/16进制转换
Qt浮点数(float)/16进制转换
Julia 复数和有理数
在 Julia 中,预定义的复数和有理数类型支持丰富的数学运算。复数表示为 `a+bi`,其中 `i` 是虚数单位,`im` 是其全局常量。例如,`1+2im` 是一个复数。可以进行算术操作,如乘法、除法、加减和幂运算,例如 `(1 + 2im)*(2 - 3im)` 返回 `8 + 1im`。此外,复数也可以进行复数次幂,如 `(-1 + 2im)^2` 结果为 `-3 - 4im`。同样,有理数表达简洁,如 `3(2 - 5im)^-1.0` 返回 `0.20689655172413796 + 0.5172413793103449im`。
|
23天前
|
人工智能 BI
MT3019 异或和的或
MT3019 异或和的或
MT2045 斐波那契,但是是字符串
MT2045 斐波那契,但是是字符串
MT3018 斐波那契数列
MT3018 斐波那契数列
|
23天前
|
算法 iOS开发
MT3041 多项式变换求值
MT3041 多项式变换求值
|
1月前
|
存储 安全 程序员
C/C++中的整数乘法运算与汇编指令MUL和IMUL
C/C++中的整数乘法运算与汇编指令MUL和IMUL
17 0