欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

华为2020秋招笔试试题

程序员文章站 2022-03-04 12:05:45
...

这两天看师姐都在忙着准备秋招,自己也去做了一下今年的华为秋招笔试题。

 

题目描述:
常用的逻辑计算有And(表示为&);Or(表示为|);Not(表示为!)。其中,他们的优先级关系是Not(!)>And(&)>Or(|)。


输入描述:
1、测试用例中间无空格,无需考虑空格。

2、测试用例表达式只会出现如下字符:“0”,“1”,“(”,“)”,“&”,“|”,“!”。

3、测试用例所给的输入都是合法输入,无需要考虑非法输入。

4、测试用例长度不会超过128个字符。

5、括号可以重复嵌套。

例如:

1 | ( 1 & 0 )                       返回值:1

1 & 0 | 0 & 1                     返回值:0

! 0 & 1 | 0                          返回值:1

( ( ! 0 & 1 ) ) | 0                 返回值:1


输出描述:
输出逻辑运算后的最终结果:0或者1

示例1:
输入:! ( 1 & 0 ) | 0 & 1

输出:1

示例2:
输入:! ( 1 & 0 ) & 0 | 0


思路:这道题我是这样想的,因为括号的性质,括号里面的总是最先计算,那我们可以用一个栈,遍历字符串的时候,前括号碰到时不做处理,只要不是后括号都入栈,遇到后括号后开始出栈直到碰到前括号,这样就保证出栈的这个字符串不包含括号,符合运算优先级规则,处理完后将这个区间的答案字符入栈。定义个函数用来处理不包含括号的字符串,遍历3次字符串,分别处理三个优先级的运算符,每次处理完更新字符串,3此循环后便是答案。

 

代码如下:

#include <iostream>
#include <string>
#include <stack>

using namespace std;

class Solution
{
public:
    string cacular(string s)
    {
        string str="";
        for(int i=0;i<s.size();i++)
        {
            if(s[i]=='!')
            {
                str+=char(!int(s[i+1]-'0')+48);
                i++;
                continue;
            }
            str+=s[i];
        }
        s=str;
        str="";
        for(int i=0;i<s.size();i++)
        {
            if(s[i]=='&')
            {
                str[str.size()-1]=char((int(str[str.size()-1]-'0')&int(s[i+1]-'0'))+48);
                i+=1;
                continue;
            }
            str+=s[i];
        }
        s=str;
        str="";
        for(int i=0;i<s.size();i++)
        {
            if(s[i]=='|')
            {
                str[str.size()-1]=char((int(str[str.size()-1]-'0')|int(s[i+1]-'0'))+48);
                i+=1;
                continue;
            }
            str+=s[i];
        }
        return str;
    }
    string fsolution(string s)
    {
        stack<char> st;
        for(int i=s.size()-1;i>=0;i--)
        {
            string str="";
            if(s[i]=='(')
            {
                while(st.top()!=')')
                {
                    str+=st.top();
                    st.pop();
                }
                st.pop();
                st.push(cacular(str)[0]);
                continue;
            }
            st.push(s[i]);
        }
        string str="";
        while(!st.empty())
        {
            str+=st.top();
            st.pop();
        }
        return cacular(str);
    }
};

int main()
{
    Solution *a=new Solution();
    string str;
    cin<<str;
    cout << a->fsolution(str) << endl;
    return 0;
}