Are they the same meaning? Or grammatically it's right? I used Grammar check online but it said both are correct. ex) You should not have believed him You should have not to believe him Which one is correct?
'You should have not to believe him' is ungrammatical. The example is better adjusted also.
'You should not have worked so late.' means 'You ought to have finished working earlier.' [usually, a friendly upbraiding]
'You should not have to work so late.' means 'You are being compelled / obliged to work beyond a reasonable time.' [usually, a comment that too much is being expected of you, though it could again be friendly upbraiding, implying that you are asking too much of yourself]
The correct structure of this sentence must be:
Subject + should + not + verb
[For this case] Subject + should + not + have + past participle
Therefore, the correct sentence is You should not have believed him.