Parentheses In Infix To RPN (Reverse Polish Notation) Not Working Correctly

SalladShooter

I believe when converting from Infix to RPN (Reverse Polish Notation) the parentheses should stay the same in Infix (surrounding the characters that go first), but when I try to convert from Infix to RPN it gives me an incorrect RPN. I can’t seem to figure out why the parentheses don’t work correctly in my code.

https://scratch.mit.edu/projects/1144197341

Last edited by SalladShooter (March 9, 2025 21:48:16)

SalladShooter

I enter the Infix of “1+2(3-4)” and it gives me “1234-(+)” when instead it should be “1234-*+”
Or for “1+2-(3-4)” it gives me “12+34-(-)” when it should be “12+34–”

SalladShooter

Not to rush anyone, but does anyone have any thoughts on my issue?

grkw2020

SalladShooter wrote:
Not to rush anyone, but does anyone have any thoughts on my issue?

Sorry, I've never heard of RPN before, so I'm just researching it.

grkw2020

So, I'm a bit confused: why does your converter output brackets? I'm currently under the impression that they are unnecessary when using RPN.

EpicGhoul993

RPN doesn't use brackets though.

I don't really know much about this topic, but found this piece of code (in Python, sadly) after some searching:
Edit: forgot to say this is to convert infix to postfix whoops

# Function to return precedence of operators
def prec(c):
    if c == '^':
        return 3
    elif c == '/' or c == '*':
        return 2
    elif c == '+' or c == '-':
        return 1
    else:
        return -1
# Function to perform infix to postfix conversion
def infixToPostfix(s):
    st = []
    result = ""
    for i in range(len(s)):
        c = s[i]
        # If the scanned character is
        # an operand, add it to the output string.
        if (c >= 'a' and c <= 'z') or (c >= 'A' and c <= 'Z') or (c >= '0' and c <= '9'):
            result += c
        # If the scanned character is an 
        # ‘(‘, push it to the stack.
        elif c == '(':
            st.append('(')
        # If the scanned character is an ‘)’,
        # pop and add to the output string from the stack 
        # until an ‘(‘ is encountered.
        elif c == ')':
            while st[-1] != '(':
                result += st.pop()
            st.pop()
        # If an operator is scanned
        else:
            while st and (prec(c) < prec(st[-1]) or prec(c) == prec(st[-1])):
                result += st.pop()
            st.append(c)
    
    # Pop all the remaining elements from the stack
    while st:
        result += st.pop()
    print(result)

Last edited by EpicGhoul993 (March 10, 2025 04:51:44)

SalladShooter

grkw2020 wrote:
So, I'm a bit confused: why does your converter output brackets? I'm currently under the impression that they are unnecessary when using RPN.

I had them output parentheses before I learned about the no parentheses, but I can’t seem to get it to out put the correct thing, because depending on the situation it should be * multiplication or another operator.

SalladShooter

SalladShooter wrote:
grkw2020 wrote:
So, I'm a bit confused: why does your converter output brackets? I'm currently under the impression that they are unnecessary when using RPN.
I had them output parentheses before I learned about the no parentheses, but I can’t seem to get it to out put the correct thing, because depending on the situation it should be * multiplication or another operator.

I can completely remove the parentheses but then it wouldn't be correct as I would need some other symbol in it's place.

grkw2020

SalladShooter wrote:
SalladShooter wrote:
grkw2020 wrote:
So, I'm a bit confused: why does your converter output brackets? I'm currently under the impression that they are unnecessary when using RPN.
I had them output parentheses before I learned about the no parentheses, but I can’t seem to get it to out put the correct thing, because depending on the situation it should be * multiplication or another operator.
I can completely remove the parentheses but then it wouldn't be correct as I would need some other symbol in it's place.

What do you mean? Could I have an example?

grkw2020

EpicGhoul993 wrote:

RPN doesn't use brackets though.

I don't really know much about this topic, but found this piece of code (in Python, sadly) after some searching:
Edit: forgot to say this is to convert infix to postfix whoops

# Function to return precedence of operators
def prec(c):
    if c == '^':
        return 3
    elif c == '/' or c == '*':
        return 2
    elif c == '+' or c == '-':
        return 1
    else:
        return -1
# Function to perform infix to postfix conversion
def infixToPostfix(s):
    st = []
    result = ""
    for i in range(len(s)):
        c = s[i]
        # If the scanned character is
        # an operand, add it to the output string.
        if (c >= 'a' and c <= 'z') or (c >= 'A' and c <= 'Z') or (c >= '0' and c <= '9'):
            result += c
        # If the scanned character is an 
        # ‘(‘, push it to the stack.
        elif c == '(':
            st.append('(')
        # If the scanned character is an ‘)’,
        # pop and add to the output string from the stack 
        # until an ‘(‘ is encountered.
        elif c == ')':
            while st[-1] != '(':
                result += st.pop()
            st.pop()
        # If an operator is scanned
        else:
            while st and (prec(c) < prec(st[-1]) or prec(c) == prec(st[-1])):
                result += st.pop()
            st.append(c)
    
    # Pop all the remaining elements from the stack
    while st:
        result += st.pop()
    print(result)

RPN is postfix. So this code should work.

Edit: I could try converting this to scratch blocks if needed

Last edited by grkw2020 (March 10, 2025 23:05:23)

SalladShooter

grkw2020 wrote:
SalladShooter wrote:
SalladShooter wrote:
grkw2020 wrote:
So, I'm a bit confused: why does your converter output brackets? I'm currently under the impression that they are unnecessary when using RPN.
I had them output parentheses before I learned about the no parentheses, but I can’t seem to get it to out put the correct thing, because depending on the situation it should be * multiplication or another operator.
I can completely remove the parentheses but then it wouldn't be correct as I would need some other symbol in it's place.
What do you mean? Could I have an example?

For instance the Infix of “1+2(3-4)” should be “12+34-*” (or something like that) or for “1+2+(3-4)” should be “12+34-+” (no multiplication here)

grkw2020

SalladShooter wrote:
grkw2020 wrote:
SalladShooter wrote:
SalladShooter wrote:
grkw2020 wrote:
So, I'm a bit confused: why does your converter output brackets? I'm currently under the impression that they are unnecessary when using RPN.
I had them output parentheses before I learned about the no parentheses, but I can’t seem to get it to out put the correct thing, because depending on the situation it should be * multiplication or another operator.
I can completely remove the parentheses but then it wouldn't be correct as I would need some other symbol in it's place.
What do you mean? Could I have an example?
For instance the Infix of “1+2(3-4)” should be “12+34-*” (or something like that) or for “1+2+(3-4)” should be “12+34-+” (no multiplication here)

I still don't understand why you need the brackets, sorry.

SalladShooter

grkw2020 wrote:
SalladShooter wrote:
grkw2020 wrote:
SalladShooter wrote:
SalladShooter wrote:
grkw2020 wrote:
So, I'm a bit confused: why does your converter output brackets? I'm currently under the impression that they are unnecessary when using RPN.
I had them output parentheses before I learned about the no parentheses, but I can’t seem to get it to out put the correct thing, because depending on the situation it should be * multiplication or another operator.
I can completely remove the parentheses but then it wouldn't be correct as I would need some other symbol in it's place.
What do you mean? Could I have an example?
For instance the Infix of “1+2(3-4)” should be “12+34-*” (or something like that) or for “1+2+(3-4)” should be “12+34-+” (no multiplication here)
I still don't understand why you need the brackets, sorry.

I am only using them in typing to allow people to write them as well as show which operations need to happen first. I am not trying to output the parentheses as an RPN output (this is my issue).

grkw2020

SalladShooter wrote:
grkw2020 wrote:
SalladShooter wrote:
grkw2020 wrote:
SalladShooter wrote:
SalladShooter wrote:
grkw2020 wrote:
So, I'm a bit confused: why does your converter output brackets? I'm currently under the impression that they are unnecessary when using RPN.
I had them output parentheses before I learned about the no parentheses, but I can’t seem to get it to out put the correct thing, because depending on the situation it should be * multiplication or another operator.
I can completely remove the parentheses but then it wouldn't be correct as I would need some other symbol in it's place.
What do you mean? Could I have an example?
For instance the Infix of “1+2(3-4)” should be “12+34-*” (or something like that) or for “1+2+(3-4)” should be “12+34-+” (no multiplication here)
I still don't understand why you need the brackets, sorry.
I am only using them in typing to allow people to write them as well as show which operations need to happen first. I am not trying to output the parentheses as an RPN output (this is my issue).

Well, to begin with, you could filter all brackets out of the output.

nembence

You can keep track of whether a left input is available
If there is a left input, then the next token can be a binary operator like a+b or a postfix unary op like n!.
If there is no left input, then the next token must be a prefix unary op like -x or a value like x or 3.
You can do that if there is a left input, but the next token doesn't accept it like 2(…) or 3x then add an implicit multiplication between them.

SalladShooter

nembence wrote:
You can keep track of whether a left input is available
If there is a left input, then the next token can be a binary operator like a+b or a postfix unary op like n!.
If there is no left input, then the next token must be a prefix unary op like -x or a value like x or 3.
You can do that if there is a left input, but the next token doesn't accept it like 2(…) or 3x then add an implicit multiplication between them.

Could you give an example of how I could do that?

nembence

SalladShooter wrote:
Could you give an example of how I could do that?

Every token can be parsed in two ways depending on if it gets left input, and then it decides if it gives input for the next token.
Every token either puts an output to the right or pulls an input from the right.

For example the "-" token can become >-< or <-< depending on if it gets left input
"3" can only become <3> which gives output in both directions


"3 * - 2 ( 1 + 4 ) - ( 5 - 6 )" becomes

start<  <3>  >*<  <-<  <2>  [×]  <(<  <1>  >+<  <4>  >)>  >-<  <(<  <5>  >-<  <6>  >)>  >end

                             ^-multiplication is inserted automatically to allow matching <2> and <(<
                               as "(" doesn't have a version that accepts left input


"2 + ( 4 * ) -" becomes

start<  <2>  >+<  <(<  <4>  >*<  [SyntaxError]  >)>  >-<  [SyntaxError]  >end

The >*< waits a right input, but ")" can't give it so something is missing in between
The >-< at the end waits an input, but it doesn't get one because it's at the end

This is the parsing process step by step: (you don't need to fully read it if you don't want, I just wrote it before the above thing and didn't want to delete it)

start: the next token gets no input, as "*1" wouldn't make sense at the start
3 : has L input: no; parsed as const 3; gives output: yes
* : has L input: yes; parsed as …*…; gives output: no (as it still waits for the second input)
- : has L input: no; parsed as -…; gives output: no
2 : has L input: no; parsed as const 2; gives output: yes
( : has L input: yes; but it shouldn't have one so insert ×, then parse it normally; gives output: no
1 : has L input: no; parsed as const 1; gives output: yes
+ : has L input: yes; parsed as …+…; gives output: no
4 : has L input: no; parsed as const 4; gives output: yes
) : has L input: yes; (also it needs the input, otherwise things like “(1+)” could happen); gives output: yes (the thing from the inside)
- : has L input: yes; parsed as …-…; gives output: no
( : has L input: no; gives output: no
5 : has L input: no; parsed as const 5; gives output: yes
- : has L input: yes; parsed as …-…; gives output: no
6 : has L input: no; parsed as const 6; gives output: yes
) : has L input: yes; gives output: yes
There is an output at the end which is good because it means it's not waiting for more operands

Discuss Scratch