signed

QiShunwang

“诚信为本、客户至上”

[每日一题]Acwing 3302. 表达式求值

2021/3/21 11:11:29   来源:

题目

给定一个表达式,其中运算符仅包含 +,-,*,/(加 减 乘 整除),可能包含括号,请你求出表达式的最终值。

注意:

数据保证给定的表达式合法。
题目保证符号 - 只作为减号出现,不会作为负号出现,例如,-1+2,(2+2)*(-(1+1)+2) 之类表达式均不会出现。
题目保证表达式中所有数字均为正整数。
题目保证表达式在中间计算过程以及结果中,均不超过 231−1。
题目中的整除是指向 0 取整,也就是说对于大于 0 的结果向下取整,例如 5/3=1,对于小于 0 的结果向上取整,例如 5/(1−4)=−1。
C++和Java中的整除默认是向零取整;Python中的整除//默认向下取整,因此Python的eval()函数中的整除也是向下取整,在本题中不能直接使用。
输入格式
共一行,为给定表达式。

输出格式
共一行,为表达式的结果。

数据范围
表达式的长度不超过 105。

输入样例:
(2+2)*(1+1)
输出样例:
8

思路

先将前缀表达式转换为后缀表达式

  1. 如果是数字,直接输出
  2. 如果是运算符,若栈顶元素也是运算符且当前运算符优先级小于栈顶运算符且栈不为空,弹出栈顶元素并输出。将当前运算符压栈。
  3. 如果当前元素是右扩号:
    1. 如果栈不为空,一直弹栈并输出直到遇到左括号
    2. 最后若栈不为空,弹出左阔号
  4. 如果是左阔号,直接压栈
  5. 输出栈中剩余元素
    // 变为后缀表达式
    for (auto iter = expression.begin(); iter != expression.end(); iter++)
    {
		// 如果是数字,直接输出
    	if (*iter >= '0' && *iter <= '9')
    	{
    		while (*iter >= '0' && *iter <= '9' && iter != expression.end())
    		{
    			p_expression.push_back(*iter);
    			iter++;
    		}
    		iter--;
    		p_expression.push_back(' ');
    	}
    	// 如果是运算符,若栈顶元素也是运算符且当前运算符优先级小于栈顶运算符且栈不为空,弹出栈顶元素并输出
    	// 将当前运算符压栈
    	else if (isp(*iter))
        {
            while ( !s1.empty() && (rankp(*iter) <= rankp(s1.top())) && isp(s1.top()) )
            {
                p_expression.push_back(s1.top());
                s1.pop();
            }
            s1.push(*iter);
        }
        // 如果当前元素是右扩号:
        // 如果栈不为空,一直弹栈并输出直到遇到左括号
        // 最后若栈不为空,弹出左阔号
        else if (*iter == ')')
        {
            while (!s1.empty() && s1.top() != '(')
            {
                p_expression.push_back(s1.top());
                s1.pop();
            }
            
            if (!s1.empty())
                s1.pop();
        }
        // 如果是左阔号,直接压栈
        else if (*iter == '(')
        {
            s1.push(*iter);
        }
    }
    // 最后输出栈中剩余元素
    while (!s1.empty())
    {
        p_expression.push_back(s1.top());
        s1.pop();
    }

计算后缀表达式的值

  1. 如果是数字,直接压栈
  2. 如果是运算符,弹出两个数字,与当前运算符左运算,将结果压入栈中
    for (auto iter = p_expression.begin(); iter != p_expression.end(); iter++)
    {
    	t = "";
        while (*iter >= '0' && *iter <= '9')
        {
        	t.push_back(*iter++);
        }

        if (t != "")
        	s2.push(atoi(t.c_str()));

        if (*iter != ' ')
        {
			int num1 = s2.top();
			s2.pop();
			int num2 = s2.top();
			s2.pop();


            if (*iter == '+')
                temp = num2 + num1;
            if (*iter == '-')
                temp = num2 - num1;
            if (*iter == '*')
                temp = num2 * num1;
            if (*iter == '/')
                temp = num2 / num1;
            s2.push(temp);
        }
    }
    if (!s2.empty())
		cout << s2.top();