Dada una string que consta de solo 0, 1, A, B, C donde
A = AND
B = OR
C = XOR
Calcular el valor de la string suponiendo que no hay orden de precedencia y que la evaluación se realiza de izquierda a derecha.
Restricciones: la longitud de la string será impar. Siempre será una string válida.
Ejemplo, 1AA0 no se dará como entrada.
Ejemplos:
Input : 1A0B1 Output : 1 1 AND 0 OR 1 = 1 Input : 1C1B1B0A0 Output : 0
Fuente: ronda en línea de Microsoft para pasantías 2017
La idea es atravesar todos los operandos saltando un carácter después de cada iteración. Para el operando actual str[i], verifique los valores de str[i+1] y str[i+2], en consecuencia, decida el valor de la subexpresión actual.
Implementación:
C++
// C++ program to evaluate value of an expression.
#include <bits/stdc++.h>
using namespace std;
int evaluateBoolExpr(string s)
{
int n = s.length();
// Traverse all operands by jumping
// a character after every iteration.
for (int i = 0; i < n; i += 2) {
// If operator next to current operand
// is AND.
if (s[i + 1] == 'A') {
if (s[i + 2] == '0'|| s[i] == '0')
s[i + 2] = '0';
else
s[i + 2] = '1';
}
// If operator next to current operand
// is OR.
else if (s[i + 1] == 'B') {
if (s[i + 2] == '1'|| s[i] == '1')
s[i + 2] = '1';
else
s[i + 2] = '0';
}
// If operator next to current operand
// is XOR (Assuming a valid input)
else {
if (s[i + 2] == s[i])
s[i + 2] = '0';
else
s[i + 2] = '1';
}
}
return s[n - 1] -'0';
}
// Driver code
int main()
{
string s = "1C1B1B0A0";
cout << evaluateBoolExpr(s);
return 0;
}
Java
// Java program to evaluate value of an expression.
public class Evaluate_BoolExp {
// Evaluates boolean expression
// and returns the result
static int evaluateBoolExpr(StringBuffer s)
{
int n = s.length();
// Traverse all operands by jumping
// a character after every iteration.
for (int i = 0; i < n; i += 2) {
// If operator next to current operand
// is AND.
if( i + 1 < n && i + 2 < n)
{
if (s.charAt(i + 1) == 'A') {
if (s.charAt(i + 2) == '0' ||
s.charAt(i) == 0)
s.setCharAt(i + 2, '0');
else
s.setCharAt(i + 2, '1');
}
// If operator next to current operand
// is OR.
else if ((i + 1) < n &&
s.charAt(i + 1 ) == 'B') {
if (s.charAt(i + 2) == '1' ||
s.charAt(i) == '1')
s.setCharAt(i + 2, '1');
else
s.setCharAt(i + 2, '0');
}
// If operator next to current operand
// is XOR (Assuming a valid input)
else {
if (s.charAt(i + 2) == s.charAt(i))
s.setCharAt(i + 2, '0');
else
s.setCharAt(i + 2 ,'1');
}
}
}
return s.charAt(n - 1) - '0';
}
// Driver code
public static void main(String[] args)
{
String s = "1C1B1B0A0";
StringBuffer sb = new StringBuffer(s);
System.out.println(evaluateBoolExpr(sb));
}
}
// This code is contributed by Sumit Ghosh
Python3
# Python3 program to evaluate value
# of an expression.
import math as mt
def evaluateBoolExpr(s):
n = len(s)
# Traverse all operands by jumping
# a character after every iteration.
for i in range(0, n - 2, 2):
# If operator next to current
# operand is AND.'''
if (s[i + 1] == "A"):
if (s[i + 2] == "0" or s[i] == "0"):
s[i + 2] = "0"
else:
s[i + 2] = "1"
# If operator next to current
# operand is OR.
else if (s[i + 1] == "B"):
if (s[i + 2] == "1" or s[i] == "1"):
s[i + 2] = "1"
else:
s[i + 2] = "0"
# If operator next to current operand
# is XOR (Assuming a valid input)
else:
if (s[i + 2] == s[i]):
s[i + 2] = "0"
else:
s[i + 2] = "1"
return ord(s[n - 1]) - ord("0")
# Driver code
s = "1C1B1B0A0"
string=[s[i] for i in range(len(s))]
print(evaluateBoolExpr(string))
# This code is contributed
# by mohit kumar 29
C#
// C# program to evaluate value
// of an expression.
using System;
using System.Text;
class GFG
{
// Evaluates boolean expression
// and returns the result
public static int evaluateBoolExpr(StringBuilder s)
{
int n = s.Length;
// Traverse all operands by jumping
// a character after every iteration.
for (int i = 0; i < n; i += 2)
{
// If operator next to current
// operand is AND.
if (i + 1 < n && i + 2 < n)
{
if (s[i + 1] == 'A')
{
if (s[i + 2] == '0' || s[i] == 0)
{
s[i + 2] = '0';
}
else
{
s[i + 2] = '1';
}
}
// If operator next to current
// operand is OR.
else if ((i + 1) < n && s[i + 1] == 'B')
{
if (s[i + 2] == '1' || s[i] == '1')
{
s[i + 2] = '1';
}
else
{
s[i + 2] = '0';
}
}
// If operator next to current operand
// is XOR (Assuming a valid input)
else
{
if (s[i + 2] == s[i])
{
s[i + 2] = '0';
}
else
{
s[i + 2] = '1';
}
}
}
}
return s[n - 1] - '0';
}
// Driver code
public static void Main(string[] args)
{
string s = "1C1B1B0A0";
StringBuilder sb = new StringBuilder(s);
Console.WriteLine(evaluateBoolExpr(sb));
}
}
// This code is contributed by Shrikant13
PHP
<?php
// PHP program to evaluate value
// of an expression.
function evaluateBoolExpr($s)
{
$n = strlen($s);
// Traverse all operands by jumping
// a character after every iteration.
for ($i = 0; $i < $n; $i += 2)
{
// If operator next to current operand
// is AND.
if (($i + 1) < $n && $s[$i + 1] == 'A')
{
if ($s[$i + 2] == '0'|| $s[$i] == '0')
$s[$i + 2] = '0';
else
$s[$i + 2] = '1';
}
// If operator next to current operand
// is OR.
else if (($i + 1) < $n && $s[$i + 1] == 'B')
{
if ($s[$i + 2] == '1'|| $s[$i] == '1')
$s[$i + 2] = '1';
else
$s[$i + 2] = '0';
}
// If operator next to current operand
// is XOR (Assuming a valid input)
else
{
if (($i + 2) < $n && $s[$i + 2] == $s[$i])
$s[$i + 2] = '0';
else
$s[$i + 2] = '1';
}
}
return $s[$n - 1] -'0';
}
// Driver code
$s = "1C1B1B0A0";
echo evaluateBoolExpr($s);
// This code is contributed
// by Akanksha Rai
Javascript
<script>
// Javascript program to evaluate
// value of an expression.
// Evaluates boolean expression
// and returns the result
function evaluateBoolExpr(s)
{
let n = s.length;
// Traverse all operands by jumping
// a character after every iteration.
for(let i = 0; i < n; i += 2)
{
// If operator next to current
// operand is AND.
if (i + 1 < n && i + 2 < n)
{
if (s[i + 1] == 'A')
{
if (s[i + 2] == '0' ||
s[i] == 0)
{
s[i + 2] = '0';
}
else
{
s[i + 2] = '1';
}
}
// If operator next to current
// operand is OR.
else if ((i + 1) < n && s[i + 1] == 'B')
{
if (s[i + 2] == '1' || s[i] == '1')
{
s[i + 2] = '1';
}
else
{
s[i + 2] = '0';
}
}
// If operator next to current operand
// is XOR (Assuming a valid input)
else
{
if (s[i + 2] == s[i])
{
s[i + 2] = '0';
}
else
{
s[i + 2] = '1';
}
}
}
}
return (s[n - 1].charCodeAt() -
'0'.charCodeAt());
}
// Driver code
let s = "1C1B1B0A0";
let sb = s.split('');
document.write(evaluateBoolExpr(sb) + "</br>");
// This code is contributed by rameshtravel07
</script>
Producción
0
Complejidad temporal: O(n)
Espacio auxiliar: O(n)
Este artículo es una contribución de Ayushi Jain . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA