华为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;
}