Facebook Interview Question SDE1s
Country: United States
using System;
using System.Collections.Generic;
using System.Linq;
using Xunit;
namespace Prefix2Postfix
{
public class Prefix2PostfixShould
{
[Theory]
[InlineData("*ab", "ab*")] // a*b
[InlineData("+a*bc", "abc*+")] // a+b*c
[InlineData("+*abc", "ab*c+")] // a*b+c
[InlineData("*+ab+cd", "ab+cd+*")] // (a + b)*(c + d)
public void Convert(string prefix, string expected)
{
var postfix = Expressions.Convert2Postfix(prefix);
Assert.Equal(expected, postfix);
}
}
public class Expressions
{
public static string Convert2Postfix(string prefix)
{
var stack = new Stack<string>();
for (int i=prefix.Length-1; i>=0; i--)
{
if (IsOperator(prefix[i]))
{
var left = stack.Pop();
var right = stack.Pop();
var res = left + right + prefix[i];
stack.Push(res);
}
else
{
stack.Push(prefix[i].ToString());
}
}
string postfix = string.Empty;
while(stack.TryPop(out var item))
{
postfix += item;
}
return postfix;
}
private static bool IsOperator(char value)
{
const string operators = "*/+-";
return operators.Contains(value);
}
}
}
Java Version of above problem:
public class ConvertPrefixToPostfix {
static String prefix = "-*+ABC*-DE+FG";
public static void main(String[] args) {
Stack<String> s = new Stack<>();
String o1 = null;
String o2 = null;
char[] prefixArry = prefix.toCharArray();
for (int i = prefixArry.length - 1; i >= 0; i--) {
if (isOperator(prefixArry[i])) {
o1 = s.pop();
o2 = s.pop();
s.push(o1 + o2 + prefixArry[i]);
} else {
s.push("" + prefixArry[i]);
}
}
StringBuilder b = new StringBuilder();
while (!s.isEmpty()){
b.append(s.pop());
}
System.out.println(b);
}
private static boolean isOperator(char c) {
return c == '+' || c == '-' || c == '*';
}
}
public class ConvertPrefixToPostfix {
static String prefix = "-*+ABC*-DE+FG";
public static void main(String[] args) {
Stack<String> s = new Stack<>();
String o1 = null;
String o2 = null;
char[] prefixArry = prefix.toCharArray();
for (int i = prefixArry.length - 1; i >= 0; i--) {
if (isOperator(prefixArry[i])) {
o1 = s.pop();
o2 = s.pop();
s.push(o1 + o2 + prefixArry[i]);
} else {
s.push("" + prefixArry[i]);
}
}
StringBuilder b = new StringBuilder();
while (!s.isEmpty()){
b.append(s.pop());
}
System.out.println(b);
}
private static boolean isOperator(char c) {
return c == '+' || c == '-' || c == '*';
}
}
The approach is the following.
- Parse each infix token
- If we find operator add to operator stack and set state to be operandAState
- If we find a character and if the state is operandAState, push character to operandA stack and set state to operandBState
- If we find a character and if the state is operandBState, then we found operandB, so take last operandA plus this new operandB character and the last operator then create a new operandA token
- Repeat until end of prefix character.
function isOperator(c) {
return "*+/-".indexOf(c) !== -1;
}
function prefixToPostfix(prefixArray) {
var operators = [];
var operandAs = [];
var operandBs = [];
var state = 0;
for(var c of prefixArray) {
if (isOperator(c)) {
operators.push(c);
state = 1;
}else if(state === 1) { //operand A found
operandAs.push(c);
state = 2;
}else { //operand B found
//found operandB, means we have operandA and operator
//so group them to be the new operandA (+AB) => (AB+)
var operator = operators.pop();
var operandA = operandAs.pop();
var operandB = c;
var newOperandA = operandA + operandB + operator;
operandAs.push(newOperandA)
state = 2;
}
}
return operandAs.concat(operators).join('');
}
var tests = [
{ input: '+AB', expected: 'AB+'},
{ input: '+A*BC', expected: 'ABC*+'},
{ input: '*+ABC', expected: 'AB+C*'},
{ input: '*+AB+CD', expected: 'AB+CD+*'},
{ input: '+*AB*CD', expected: 'AB*CD*+'},
{ input: '+++ABCD', expected: 'AB+C+D+'},
].forEach( (test, index) => {
var postfix = prefixToPostfix(test.input);
var isExpected = postfix === test.expected;
console.log('Test: ' + index + ' passed = ' + isExpected);
});
Swift recursive answer.
import Foundation
func isOperator(character: String) -> Bool {
switch character {
case "+", "-", "*", "/":
return true
default:
return false
}
}
func preToPost(pre: inout String) -> String {
let first = String(pre.removeFirst())
if isOperator(character: first) {
return preToPost(pre: &pre) + // left operand
preToPost(pre: &pre) + // right operand
first // operator
} else {
return first // operand
}
}
var a = "+*AB/CD"
print(preToPost(pre: &a)) // "AB*CD/+"
var b = "/*A+BCD"
print(preToPost(pre: &b)) // "ABC+*D/"
var c = "*A+B/CD"
print(preToPost(pre: &c)) // "ABCD/+*"
My recursive solution:
string prefixToPostfix(const string& s) {
auto it = s.cbegin();
auto nextChar = [&]() -> optional<char> {
return it == s.cend() ? optional<char>() : *(it++);
};
auto isOperator = [](char c) -> bool {
return c == '*' || c == '/' || c == '+' || c == '-';
};
string r;
function<void(void)> convert = [&]() -> void {
auto c = nextChar();
if (!c) throw runtime_error("unexpected eof");
if (isOperator(*c)) {
convert();
convert();
}
r.push_back(*c);
};
convert();
if (it != s.cend()) throw runtime_error("unexpected eof");
return r;
}
- harrypotter0 September 16, 2017#include <bits/stdc++.h> using namespace std; bool isOperator(char c) { if(c == '+' || c == '-' || c == '*' || c == '/') // you may add operator here return true; return false; } int main() { string prefix; cin >> prefix; stack<string> st; string t1, t2; int l = prefix.length(); for (int i = l - 1; i >= 0; i--) { if (isOperator(prefix[i])) { t1 = st.top(); st.pop(); t2 = st.top(); st.pop(); t2 += prefix[i]; st.push(t1 + t2); } else { t1 = ""; t1 += prefix[i]; st.push(t1); } } string postfix = st.top(); st.pop(); cout << postfix << endl; } /* Sample Input : -*+ABC*-DE+FG Sample Output : AB+C*DE-FG+*- */