Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Stack & Queue

Infix to Postfix

Medium · Stack & Queue · Asked at Amazon, Microsoft, Samsung, TCS, Infosys

Convert the infix expression to postfix (reverse Polish) notation. Operands are single lowercase letters. Operators are + - (lowest), * /, and ^ (highest). ^ is right-associative; the others are left-associative. Parentheses may appear.

Input

A single line: the expression (no spaces).

Output

The postfix expression (no spaces).

Constraints

Shunting-yard: output operands directly; push "("; on ")" pop until "("; on an operator, pop operators with higher precedence (or equal precedence if the new one is left-associative) first.

Example 1

Input

a+b*(c^d-e)^(f+g*h)-i

Output

abcd^e-fgh*+^*+i-

Example 2

Input

a^b^c

Output

abc^^

Hints

  1. Operands go straight to the output. Operators wait on a stack.
  2. Before pushing an operator, pop operators with higher precedence — and with equal precedence too, unless the new operator is the right-associative ^.

Approach

Shunting-yard. Letters → output. "(" → push. ")" → pop to output until "(", then discard it. Operator o: while the top is an operator t with prec(t) > prec(o), or prec(t) == prec(o) and o is left-associative, pop t to output; then push o. At the end pop everything. Right associativity of ^ is exactly why "a^b^c" becomes "abc^^".

Complexity: O(n) time · O(n) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int prec(char c) {
    if (c == '+' || c == '-') return 1;
    if (c == '*' || c == '/') return 2;
    return 3;
}

int main() {
    string s, out;
    cin >> s;
    string ops;
    for (char c : s) {
        if (isalpha((unsigned char)c)) out += c;
        else if (c == '(') ops += c;
        else if (c == ')') {
            while (ops.back() != '(') out += ops.back(), ops.pop_back();
            ops.pop_back();
        } else {
            while (!ops.empty() && ops.back() != '(' &&
                   (prec(ops.back()) > prec(c) || (prec(ops.back()) == prec(c) && c != '^'))) {
                out += ops.back();
                ops.pop_back();
            }
            ops += c;
        }
    }
    while (!ops.empty()) out += ops.back(), ops.pop_back();
    cout << out << "\n";
    return 0;
}

Python solution

s = input().strip()
prec = {"+": 1, "-": 1, "*": 2, "/": 2, "^": 3}
out, ops = [], []
for c in s:
    if c.isalpha():
        out.append(c)
    elif c == "(":
        ops.append(c)
    elif c == ")":
        while ops[-1] != "(":
            out.append(ops.pop())
        ops.pop()
    else:
        while ops and ops[-1] != "(" and (prec[ops[-1]] > prec[c] or (prec[ops[-1]] == prec[c] and c != "^")):
            out.append(ops.pop())
        ops.append(c)
while ops:
    out.append(ops.pop())
print("".join(out))

Java solution

import java.util.*;

public class Main {
    static int prec(char c) {
        if (c == '+' || c == '-') return 1;
        if (c == '*' || c == '/') return 2;
        return 3;
    }

    public static void main(String[] args) {
        String s = new Scanner(System.in).next();
        StringBuilder out = new StringBuilder();
        Deque<Character> ops = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            if (Character.isLetter(c)) out.append(c);
            else if (c == '(') ops.push(c);
            else if (c == ')') {
                while (ops.peek() != '(') out.append(ops.pop());
                ops.pop();
            } else {
                while (!ops.isEmpty() && ops.peek() != '(' &&
                       (prec(ops.peek()) > prec(c) || (prec(ops.peek()) == prec(c) && c != '^'))) out.append(ops.pop());
                ops.push(c);
            }
        }
        while (!ops.isEmpty()) out.append(ops.pop());
        System.out.println(out);
    }
}

Solve Infix to Postfix online · All practice problems