How to convert Infix notation to postfix notation

[Curtis Dyer]

Wow.

Oh, I see. You're trying to sneakily imply that I'm stupid.
No, not buying it. I certainly have my cognitive flaws, but
"stupidity" is not one of them.

Am I interpreting spinoza1111's remark here correctly? It also
seems he is slighting programmers who work on embedded systems. I
suppose this shouldn't be surprising, but it's just so painfully
absurd. The many contributions of embedded systems programmers (I'm
not one, but do admire them) are demonstrably undeniable.

<snip>

 

[spinoza1111]

This post contains the promised C code version of the infix to Polish
notation convertor. When run from the command line it should execute
all cases used to test the C Sharp version correctly. Its string
handling is simpler owing to the limitations of C.

This code unless it is seriously fucked up demonstrates the
practicality of using a formal language based approach to infix to
Polish notation. It's also part of my project of relearning C.

Comments as opposed to BS welcome.


#include <stdio.H>

#include <stdlib.H>

#define MAX_POLISH_LENGTH 100

int errorHandler(char *strMessage)
{
printf("\n%s\n", strMessage); return 0;
}

int errorHandlerSyntax(int intIndex, char *strMessage)
{
printf("\nError at character %d: %s\n",
intIndex,
strMessage);
return 0;
}

int stringLength(char *strInstring)
{
int intIndex1;
for (intIndex1 = 0;
strInstring[intIndex1] != '\0';
intIndex1++) { }
return intIndex1;
}

int stringAppendChar(char *strInstring,
char chrNew,
int intMaxLength)
{
int intLength = stringLength(strInstring);
if (intLength >= intMaxLength - 1)
{
errorHandler
("Cannot append character: string too long");
return 0;
}
strInstring[intLength] = chrNew;
strInstring[intLength + 1] = '\0';
return -1;
}

int appendPolish(char *strPolish, char chrNext)
{
return
((*strPolish == '\0' || *strPolish == ' ')
?
-1
:
stringAppendChar(strPolish,
' ',
MAX_POLISH_LENGTH))
&&
stringAppendChar(strPolish,
chrNext,
MAX_POLISH_LENGTH)
&&
stringAppendChar(strPolish, ' ', MAX_POLISH_LENGTH);
}

int expression(char *strInfix,
char *strPolish,
int *intPtrIndex,
int intEnd);

int mulFactor(char *strInfix,
char *strPolish,
int *intPtrIndex,
int intEnd)
{ /* mulFactor = LETTER | NUMBER | '(' expression ')' */
int intIndexStart = 0;
int intLevel = 0;
char chrNext = ' ';
int intInner;
if (*intPtrIndex > intEnd)
return errorHandlerSyntax(*intPtrIndex,
"mulFactor unavailable");
chrNext = strInfix[*intPtrIndex];
if (chrNext >= 'a' && chrNext <= 'z')
{
(*intPtrIndex)++;
return appendPolish(strPolish, chrNext);
}
intIndexStart = *intPtrIndex;
while(*intPtrIndex <= intEnd
&&
(chrNext = strInfix[*intPtrIndex]) >= '0'
&&
chrNext <= '9')
{
if (!stringAppendChar(strPolish,
chrNext,
MAX_POLISH_LENGTH))
return 0;
(*intPtrIndex)++;
}
if (*intPtrIndex > intIndexStart)
return stringAppendChar(strPolish,
' ',
MAX_POLISH_LENGTH);
if (chrNext == '(')
{
intLevel = 1;
(*intPtrIndex)++;
intInner = *intPtrIndex;
while (intLevel > 0 && *intPtrIndex <= intEnd)
{
if ((chrNext = strInfix[(*intPtrIndex)++]) == '(')
{
intLevel++;
}
else
{
if (chrNext == ')')
{
intLevel--;
}
}
}
if (intLevel > 0)
return errorHandlerSyntax
(intInner - 1,
"Unbalanced left parenthesis");
if (!expression(strInfix,
strPolish,
&intInner,
*intPtrIndex - 2))
return errorHandlerSyntax
(intInner,
"Expression doesn't appear in parentheses");
//(*intPtrIndex)++;
return -1;
}
return 0;
}

int addFactor(char *strInfix,
char *strPolish,
int *intPtrIndex,
int intEnd)
{ /* addFactor = mulFactor [ *|/ mulFactor ] */
char chrMulOp = ' ';
int intStartIndex = 0;
if (!mulFactor(strInfix, strPolish, intPtrIndex, intEnd))
{
errorHandlerSyntax(*intPtrIndex, "mulFactor not found");
return 0;
}
if (*intPtrIndex > intEnd) return -1;
intStartIndex = *intPtrIndex;
while (*intPtrIndex <= intEnd)
{
if ((chrMulOp = strInfix[*intPtrIndex]) != '*'
&&
chrMulOp != '/')
return -1;
(*intPtrIndex)++;
if (*intPtrIndex > intEnd
||
!mulFactor(strInfix,
strPolish,
intPtrIndex,
intEnd))
return errorHandlerSyntax
(*intPtrIndex,
"Mul/div op not followed by mulFactor");
if (!appendPolish(strPolish, chrMulOp)) return 0;
}
return -1;
}

int expression(char *strInfix,
char *strPolish,
int *intPtrIndex,
int intEnd)
{ /* expression = addFactor [ +|- addFactor ] */
char chrAddOp = ' ';
int intStartIndex = 0;
if (!addFactor(strInfix, strPolish, intPtrIndex, intEnd))
{
errorHandlerSyntax(*intPtrIndex, "addFactor not found");
return 0;
}
intStartIndex = *intPtrIndex;
while (*intPtrIndex <= intEnd)
{
if ((chrAddOp = strInfix[*intPtrIndex]) != '+'
&&
chrAddOp != '-')
return -1;
(*intPtrIndex)++;
if (*intPtrIndex > intEnd
||
!addFactor(strInfix,
strPolish,
intPtrIndex,
intEnd))
return errorHandlerSyntax
(*intPtrIndex,
"Add/sub op not followed by addFactor");
appendPolish(strPolish, chrAddOp);
}
return -1;
}

char *infix2Polish(char *strInfix)
{
int intIndex = 0;
char *strPolish = malloc(MAX_POLISH_LENGTH);
if (strPolish == 0)
errorHandler("Can't get storage");
strPolish[0] = '\0';
if (!expression(strInfix,
strPolish,
&intIndex,
stringLength(strInfix) - 1))
{
errorHandler("Can't parse expression");
return "";
}
return strPolish;
}

void tester()
{
printf("Expect 10 113 + a *: %s\n",
infix2Polish("(10+113)*a"));
printf("Expect error (see above): %s\n",
infix2Polish("("));
printf("Expect error (see above): %s\n",
infix2Polish("((((2"));
printf("Expect error (see above): %s\n",
infix2Polish("////2"));
printf("Expect error (see above): %s\n",
infix2Polish(""));
printf("Expect error (see above): %s\n",
infix2Polish("("));
printf("Expect error (see above): %s\n",
infix2Polish("()"));
printf("Expect error (see above): %s\n",
infix2Polish("(((5))"));
printf("Expect 5: %s\n",
infix2Polish("(((5)))"));
printf("Expect 5: %s\n",
infix2Polish("((5))"));
printf("Expect 10 113 2 2 4 3 + / + 2 + 2 + - + a *: %s\n",
infix2Polish("((10+(113-(2+((((((2/(4+3)))))))+2+2))))*a"));
printf("Expect 1: %s\n",
infix2Polish("1"));
printf("Expect 1 1 +: %s\n",
infix2Polish("1+1"));
printf("Expect a: %s\n",
infix2Polish("a"));
printf("Expect a b +: %s\n",
infix2Polish("a+b"));
}

int main(int intArgCount, char **strArgs)
{
tester();
return;
}

 

[Nick Keighley]

Am I interpreting spinoza1111's remark here correctly?  It also
seems he is slighting programmers who work on embedded systems.  I
suppose this shouldn't be surprising, but it's just so painfully
absurd.  The many contributions of embedded systems programmers (I'm
not one, but do admire them) are demonstrably undeniable.

in many cases I'd be much more scared of bad programming practices in
an embedded system (think anti-lock brakes) than in a Microsoft box.

 

[Nick Keighley]

Furthermore, the idea that computer languages are even distinct is
absurd. That they are is a historical accident, caused by the large
number of errors made in language design in the early days.

Insofar as "knowledge" of C is knowledge of mistakes, C has no
standing as an academic subject and should not be spoken of as a
computer language. Instead, it should be considered a pathology which
computer scientists must learn for the same reason doctors must learn
cancer.

People whose main claim to expertise in C should be sent to re-
education camps on the model of UN centres in Africa which train
former guerrillas in useful trades.

And the world still needs one programming language that can be used by
everyone. The guy on the screen in the 1984 Apple commercial was
right.

Could you review this? (the utility library only provides the unit-
test and display-line functions)


*********************************************************************

;;; infix_postfix.scm
;;;
;;; infix to postscript converter

(load "library/utilities.scm")


;;;
;;; stack
(define (_stack-list s) (car s)) ; for internal use
(define (make-stack) '(()))
(define (stack-empty? s) (null? (_stack-list s)))
(define (stack-push! s item) (set-car! s (cons item (_stack-list s))))
(define (stack-top s)
(if (stack-empty? s) (error "empty stack"))
(car (_stack-list s)))
(define (stack-pop! s)
(let ((top (stack-top s)))
(set-car! s (cdr (_stack-list s)))
top))

;;;
;;; queue
; BEWARE: make-queue etc. are built-ins in chicken scheme
(define (_q-list q) (car q)) ; for internal use
(define (make-q) '(()))
(define (clear-q q) (set-car! q '()))
(define (q-empty? q) (null? (_q-list q)))

(define (q-add! q item)
(let ((new-q (append (_q-list q) (list item))))
(set-car! q new-q)))

(define (q-remove! q)
(if (q-empty? q) (error "empty queue"))
(let ((item (car (_q-list q))))
(set-car! q (cdr (_q-list q)))
item))

(define (q->list q) (_q-list q))


;;;
;;; token-stream
(define (make-tokstream s) (list s))

(define (tokstream-get! ts)
(define (empty? s) (zero? (string-length s)))
(let loop ((s (car ts)))
(if (empty? s)
'()
(let ((first (string-ref s 0)))
(if (char=? first #\space)
(loop (substring s 1 (string-length s)))
(begin
(set-car! ts (substring s 1 (string-length
s)))
first))))))

(define (tokstream->list ts) (car ts))


;;;
;;; infix to postfix conversion

;; the operators and their precedence
(define operators '((#\+ 1) (#\- 1) (#\* 2) (#\/ 2)))


;; converts infix to postfix using Dijkstra's Shunting Yard algorithm
;; the algorithm is from the Wikipedia article on the algorithm
(define (infix->postfix infix)
(let (
(in (make-tokstream infix))
(stack (make-stack))
(output (make-q)))

(define (operand? tok) (char-alphabetic? tok))
(define (operator? tok) (assq tok operators))
(define (open-brak? tok) (char=? tok #\()) ; beware
confuses syntax hiliter
(define (close-brak? tok) (char=? tok #\))) ; beware
confuses syntax hiliter
(define (precedence op) (cadr (assq op operators)))
(define (do-operand token) (q-add! output token))
(define (do-open-brak tok) (stack-push! stack tok))

(define (do-close-brak tok)
(let until-open-brak ((x '()))
(if (stack-empty? stack) (error "missing closing
bracket"))
(if (open-brak? (stack-top stack))
(stack-pop! stack) ; discard bracket
(begin
(q-add! output (stack-pop! stack))
(until-open-brak '())))))

(define (do-operator token)
(let while-operators ((x '()))
(if (and (not (stack-empty? stack)) (operator? (stack-
top stack)))
(if (<= (precedence token) (precedence (stack-top
stack)) )
(begin
(q-add! output (stack-pop! stack))
(while-operators x)))))
(stack-push! stack token))

(define (flush-stack)
(let loop ((x '())) ; x is a dummy argument
(if (not (stack-empty? stack))
(if (or (open-brak? (stack-top stack))
(close-brak? (stack-top stack)))
(error "infix->postfix: mismatched bracket")
(begin
(q-add! output (stack-pop! stack))
(loop '())
)))))

; turn the output queue into a string
(define (create-output-string)
(let loop ((s ""))
(if (not (q-empty? output))
(loop (string-append
s
(if (zero? (string-length s)) "" " ")
(string (q-remove! output))))
s)))

(define (trace-me token)
(display-line "infix-postfix: processing token" token
"stream" (tokstream->list in)
"output" (q->list output)))

; infix->postfix body
(clear-q output) ; bug work-around
(if (not (q-empty? output)) (error "output queue not empty!"))
(let while-tokens ((token (tokstream-get! in)))
;(trace-me token)
(if (not (null? token))
(begin
(cond
((operand? token) (do-operand token))
((operator? token) (do-operator token))
((open-brak? token) (do-open-brak token))
((close-brak? token) (do-close-brak token))
(else (error "unrecognised token")))
(while-tokens (tokstream-get! in)))))

; no more tokens
(flush-stack)
(create-output-string)
)) ; end infix->postfix


;;;
;;; test harness

(define (test-infix->postfix)
(unit-test infix->postfix string=? ("a + b * c") "a b c * +")
(unit-test infix->postfix string=? ("a + b - c") "a b + c -")
(unit-test infix->postfix string=? ("a * b - c") "a b * c -")
(unit-test infix->postfix string=? ("(a + b) * c") "a b + c *")
(unit-test infix->postfix string=? ("(a+b)+z-(c/d)") "a b + z + c
d / -")
'all-tests-ok)


*********************************************************************

This version doesn't handle numbers, function calls or right-
associative operators. The trace-me was used for debugging

 

[spinoza1111]

Could you review this? (the utility library only provides the unit-
test and display-line functions)

*********************************************************************

;;; infix_postfix.scm
;;;
;;; infix to postscript converter

(load "library/utilities.scm")

;;;
;;; stack
(define (_stack-list s) (car s))   ; for internal use
(define (make-stack) '(()))
(define (stack-empty? s) (null? (_stack-list s)))
(define (stack-push! s item) (set-car! s (cons item (_stack-list s))))
(define (stack-top s)
    (if (stack-empty? s) (error "empty stack"))
    (car (_stack-list s)))
(define (stack-pop! s)
    (let ((top (stack-top s)))
        (set-car! s (cdr (_stack-list s)))
        top))

;;;
;;; queue
; BEWARE: make-queue etc. are built-ins in chicken scheme
(define (_q-list q) (car q))   ; for internal use
(define (make-q) '(()))
(define (clear-q q) (set-car! q '()))
(define (q-empty? q) (null? (_q-list q)))

(define (q-add! q item)
    (let ((new-q (append (_q-list q) (list item))))
        (set-car! q new-q)))

(define (q-remove! q)
    (if (q-empty? q) (error "empty queue"))
    (let ((item (car (_q-list q))))
        (set-car! q (cdr (_q-list q)))
        item))

(define (q->list q) (_q-list q))

;;;
;;; token-stream
(define (make-tokstream s) (list s))

(define (tokstream-get! ts)
    (define (empty? s) (zero? (string-length s)))
    (let loop ((s (car ts)))
        (if (empty? s)
            '()
            (let ((first (string-ref s 0)))
                (if (char=? first #\space)
                    (loop (substring s 1 (string-length s)))
                    (begin
                        (set-car! ts (substring s 1 (string-length
s)))
                        first))))))

(define (tokstream->list ts) (car ts))

;;;
;;; infix to postfix conversion

;; the operators and their precedence
(define operators '((#\+ 1) (#\- 1) (#\* 2) (#\/ 2)))

;; converts infix to postfix using Dijkstra's Shunting Yard algorithm
;; the algorithm is from the Wikipedia article on the algorithm
(define (infix->postfix infix)
    (let (
        (in (make-tokstream infix))
        (stack (make-stack))
        (output (make-q)))

        (define (operand? tok) (char-alphabetic? tok))
        (define (operator? tok) (assq tok operators))
        (define (open-brak? tok) (char=? tok #\())    ; beware
confuses syntax hiliter
        (define (close-brak? tok) (char=? tok #\)))   ; beware
confuses syntax hiliter
        (define (precedence op) (cadr (assq op operators)))
        (define (do-operand token) (q-add! output token))
        (define (do-open-brak tok) (stack-push! stack tok))

        (define (do-close-brak tok)
            (let until-open-brak ((x '()))
                (if (stack-empty? stack) (error "missing closing
bracket"))
                (if (open-brak? (stack-top stack))
                    (stack-pop! stack)   ; discard bracket
                    (begin
                        (q-add! output (stack-pop! stack))
                        (until-open-brak '())))))

        (define (do-operator token)
            (let while-operators ((x '()))
                (if (and (not (stack-empty? stack)) (operator? (stack-
top stack)))
                    (if (<= (precedence token) (precedence (stack-top
stack)) )
                        (begin
                            (q-add! output (stack-pop! stack))
                            (while-operators x)))))
            (stack-push! stack token))

        (define (flush-stack)
            (let loop ((x '()))   ; x is a dummy argument
                (if (not (stack-empty? stack))
                    (if (or (open-brak? (stack-top stack))
                            (close-brak? (stack-top stack)))
                        (error "infix->postfix: mismatched bracket")
                        (begin
                            (q-add! output (stack-pop! stack))
                            (loop '())
                         )))))

        ; turn the output queue into a string
        (define (create-output-string)
            (let loop ((s ""))
                (if (not (q-empty? output))
                    (loop (string-append
                        s
                        (if (zero? (string-length s)) "" " ")
                        (string (q-remove! output))))
                    s)))

        (define (trace-me token)
            (display-line "infix-postfix: processing token" token
                "stream" (tokstream->list in)
                "output" (q->list output)))

        ; infix->postfix body
        (clear-q output)   ; bug work-around
        (if (not (q-empty? output)) (error "output queue not empty!"))
        (let while-tokens ((token (tokstream-get! in)))
            ;(trace-me token)
            (if (not (null? token))
                (begin
                    (cond
                        ((operand? token) (do-operand token))
                        ((operator? token) (do-operator token))
                        ((open-brak? token) (do-open-brak token))
                        ((close-brak? token) (do-close-brak token))
                        (else (error "unrecognised token")))
                    (while-tokens (tokstream-get! in)))))

        ; no more tokens
        (flush-stack)
        (create-output-string)
))   ; end infix->postfix

;;;
;;; test harness

(define (test-infix->postfix)
    (unit-test infix->postfix string=? ("a + b * c") "a b c * +")
    (unit-test infix->postfix string=? ("a + b - c") "a b + c -")
    (unit-test infix->postfix string=? ("a * b - c") "a b * c -")
    (unit-test infix->postfix string=? ("(a + b) * c") "a b + c *")
    (unit-test infix->postfix string=? ("(a+b)+z-(c/d)") "a b + z + c
d / -")
    'all-tests-ok)

*********************************************************************

This version doesn't handle numbers, function calls or right-
associative operators. The trace-me was used for debugging- Hide quoted text -

- Show quoted text -

Sure, if you pay me or review my C infix2Polish conversion.

 

[Gene]

i have a string as (a+b)+8-(c/d) in Infix form.

how can i convert it to postfix form using C language,,,????

I suppose that if this is homework, the due date has passed.

// Convert ;-separated infix expressions on stdin to postfix on
stdout.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdarg.h>

// error handler

void die(char *msg)
{
fprintf(stderr, "\ndie: %s\n", msg);
exit(1);
}

// scanner

int lookahead;

int peek() { return lookahead; }

int peek_is(char *set)
{
return strchr(set, peek()) != NULL;
}

void advance(void)
{
do lookahead = getchar(); while (isspace(lookahead));
}

// parser for gramar:
// expr -> term { [+-] term }
// term -> factor { [*/] factor }
// factor -> ALNUM | "(" expr ")"

void term(void);
void factor(void);

void expr(void)
{
term();
while (peek_is("+-")) {
int op = peek();
advance();
term();
printf("%c", op);
}
}

void term(void)
{
factor();
while (peek_is("*/")) {
int op = peek();
advance();
factor();
printf("%c", op);
}
}

void factor(void)
{
if (isalnum(peek())) {
int literal = peek();
advance();
printf("%c", literal);
}
else if (peek() == '(') {
advance();
expr();
if (!peek_is(")")) die("expected )");
advance();
}
else
die("expected factor");
}

// user interface

int main(void)
{
advance();
do {
expr();
if (!peek_is(";")) die("expected ;");
printf("\n");
advance();
} while (peek() != EOF);
return 0;
}

 

[Nick Keighley]

Sure, if you pay me or review my C infix2Polish conversion

but, I wasn't claiming that knowledge of one language automatically
implied knowledge of another. Or that all languages were "essentially
the same"

 

[Tim Streater]

This post contains the promised C code version of the infix to Polish
notation convertor.

Promised to whom? I didn't ask for it.

 

[Tim Streater]

Am I interpreting spinoza1111's remark here correctly? It also
seems he is slighting programmers who work on embedded systems. I
suppose this shouldn't be surprising, but it's just so painfully
absurd. The many contributions of embedded systems programmers (I'm
not one, but do admire them) are demonstrably undeniable.

He sneers constantly at non-academic programmers, near as I can tell.
That seems to be anyone who cannot do the Computer Science equivalent of
deducing the properties of the universe from the definition of a point.
Then he wonders why we sneer at him.

In the 18th century, people used to visit Bedlam with pointed sticks,
poking the lunatics inside to make them gibber. With Spinny, even that
is unnecessary. Any rational response causes him to gibber
uncontrollably.

Watching Spinny's train of "logic", I'm reminded of the Soviets'
constant denigration of the West as "warmongers", the rationale for
which which went something like as follows:

1) We are in conflict with you
2) If you were to agree with our point of view, the conflict would cease
3) Since you choose not to take an action which would remove the
conflict, you are actively seeking to prolong the conflict
4) In actively seeking to prolong the conflict, you are therefore a
warmonger

There must be a word which describes this sort of thought process.

 

[Tim Streater]

And you are who exactly?

And why would you be so concerned as to who it was promised for? Or do
all posts needs to be cleared by your good self first?

Nice one.

I'm just here for the show.

 

[spinoza1111]

i have a string as (a+b)+8-(c/d) in Infix form.

how can i convert it to postfix form using C language,,,????

I suppose that if this is homework, the due date has passed.

// Convert ;-separated infix expressions on stdin to postfix on
stdout.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdarg.h>

// error handler

void die(char *msg)
{
  fprintf(stderr, "\ndie: %s\n", msg);
  exit(1);

}

// scanner

int lookahead;

int peek() { return lookahead; }

int peek_is(char *set)
{
  return strchr(set, peek()) != NULL;

}

void advance(void)
{
  do lookahead = getchar(); while (isspace(lookahead));

}

// parser for gramar:
// expr -> term { [+-] term }
// term -> factor { [*/] factor }
// factor -> ALNUM | "(" expr ")"

void term(void);
void factor(void);

void expr(void)
{
  term();
  while (peek_is("+-")) {
    int op = peek();
    advance();
    term();
    printf("%c", op);
  }

}

void term(void)
{
  factor();
  while (peek_is("*/")) {
    int op = peek();
    advance();
    factor();
    printf("%c", op);
  }

}

void factor(void)
{
  if (isalnum(peek())) {
    int literal = peek();
    advance();
    printf("%c", literal);
  }
  else if (peek() == '(') {
    advance();
    expr();
    if (!peek_is(")")) die("expected )");
    advance();
  }
  else
    die("expected factor");

}

// user interface

int main(void)
{
  advance();
  do {
    expr();
    if (!peek_is(";")) die("expected ;");
    printf("\n");
    advance();
  } while (peek() != EOF);
  return 0;



}- Hide quoted text -

- Show quoted text -

Thanks for this. Looks like you stole my approach, but I find that
most gratifying if true, and an indication that "great minds think
alike" if not. Your contribution at a minimum is to show just how
gnomic and terse one can be in C. It would not be appropriate to
credit me since it is a common and solid algorithm that has been
around for years.

Hope you don't mind, but I'm going to copy this code and incorporate
it in what will not be a three way test: of my C Sharp version, my C
version and your gnomic C. I want to add more testing (using a random
generator in C Sharp), a GUI and timing comparisions and shall report
back.

 

[spinoza1111]

i have a string as (a+b)+8-(c/d) in Infix form.

how can i convert it to postfix form using C language,,,????

I suppose that if this is homework, the due date has passed.

// Convert ;-separated infix expressions on stdin to postfix on
stdout.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdarg.h>

// error handler

void die(char *msg)
{
  fprintf(stderr, "\ndie: %s\n", msg);
  exit(1);

}

// scanner

int lookahead;

int peek() { return lookahead; }

int peek_is(char *set)
{
  return strchr(set, peek()) != NULL;

}

void advance(void)
{
  do lookahead = getchar(); while (isspace(lookahead));

}

// parser for gramar:
// expr -> term { [+-] term }
// term -> factor { [*/] factor }

Again it looks like you stole this, and again I forgive you, or ask
your forgiveness if I have accused you falsely. If you swiped it from
my grammar, you forgot to put an asterisk after the right curley
braces to indicate that there can be zero, one or more occurences of
the term or factor, preceded by its binary operator.

If you did not swipe it, then you may be using curley braces to
indicate zero one or more repetitions of the braced content; but this
would be your unique idiom, I've never seen it.

Your code supports zero one or more and this looks correct.

Also, the standard meaning of square brackets is that the bracketed
material is optional: but the binary operators you have bracketed are
most assuredly not optional as I think you know.

 

[Tim Streater]

So you're nothing more than a Regency lout?

Doesn't matter what I am, you gibber all the same.

This logic merely mirrored that of the West. The question is "who
started it". As it happened, the West started the Cold War in 1950 by
arming the Greek right wing, resulting in the murder of a Western
journalist, several years of slaughter in Greece, and military
dictatorship in that country.

The question of "who started it" is not in any way relevant to their
subsequent thought process.

 

[spinoza1111]

He sneers constantly at non-academic programmers, near as I can tell.
That seems to be anyone who cannot do the Computer Science equivalent of
deducing the properties of the universe from the definition of a point.
Then he wonders why we sneer at him.

In the 18th century, people used to visit Bedlam with pointed sticks,
poking the lunatics inside to make them gibber. With Spinny, even that
is unnecessary. Any rational response causes him to gibber
uncontrollably.

So you're nothing more than a Regency lout?

Watching Spinny's train of "logic", I'm reminded of the Soviets'
constant denigration of the West as "warmongers", the rationale for
which which went something like as follows:

1) We are in conflict with you
2) If you were to agree with our point of view, the conflict would cease
3) Since you choose not to take an action which would remove the
conflict, you are actively seeking to prolong the conflict
4) In actively seeking to prolong the conflict, you are therefore a
warmonger

This logic merely mirrored that of the West. The question is "who
started it". As it happened, the West started the Cold War in 1950 by
arming the Greek right wing, resulting in the murder of a Western
journalist, several years of slaughter in Greece, and military
dictatorship in that country.

I find here that friendly attempts to discuss code are met by the
creation of a permanent record which could threaten my employment. As
it happens, I am good at what I do, and this includes more than being
a code monkey, so in fact my Internet record has never harmed my
employment and has gotten my hired at at least one job

But I find other people including real contributors like Navia being
treated in like fashion. I also have "inside" information on the
effect of the anti-Schildt campaign, long a staple of clc, the sources
of which I am not at liberty to disclose, and this effect amounts to
that of civil and criminal libel under UK and American law.

Next time do your homework.

 

[Kenny McCormack]

And you are who exactly?

And why would you be so concerned as to who it was promised for? Or do
all posts needs to be cleared by your good self first?

It really makes the regs (and, most especially, the reg-wannabees like
Mr. Streater here) nervous to be seen as in any way requesting anything
(other than order-in-the-court, of course). That is, it destroys their
game to be seen as being in the position of asking for something as
opposed to always being the givers of knowledge.

Notice the recent hoo-hah about whether or not Kiki/RH had requested
anything from Jacob. Notice how much virtual ink was expended
discussing what was, in fact, just a small, jocular, off-the-cuff remark
from Jacob.

Kiki was obviously much distressed by both of the following
implications, and spared no effort to try to dispel both:

1) That they (Kiki and/or RH) had requested something from lowly Jacob.
2) That, in response to and in fulfillment of said request, Jacob
had actually, out of the goodness of his heart, produced something
of value.

 

[Gene]

I suppose that if this is homework, the due date has passed.

// Convert ;-separated infix expressions on stdin to postfix on
stdout.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdarg.h>

// error handler

void die(char *msg)
{
  fprintf(stderr, "\ndie: %s\n", msg);
  exit(1);

// scanner

int lookahead;

int peek() { return lookahead; }

int peek_is(char *set)
{
  return strchr(set, peek()) != NULL;

}

void advance(void)
{
  do lookahead = getchar(); while (isspace(lookahead));

}

// parser for gramar:
// expr -> term { [+-] term }
// term -> factor { [*/] factor }
// factor -> ALNUM | "(" expr ")"

void term(void);
void factor(void);

void expr(void)
{
  term();
  while (peek_is("+-")) {
    int op = peek();
    advance();
    term();
    printf("%c", op);
  }

void term(void)
{
  factor();
  while (peek_is("*/")) {
    int op = peek();
    advance();
    factor();
    printf("%c", op);
  }

void factor(void)
{
  if (isalnum(peek())) {
    int literal = peek();
    advance();
    printf("%c", literal);
  }
  else if (peek() == '(') {
    advance();
    expr();
    if (!peek_is(")")) die("expected )");
    advance();
  }
  else
    die("expected factor");

// user interface

int main(void)
{
  advance();
  do {
    expr();
    if (!peek_is(";")) die("expected ;");
    printf("\n");
    advance();
  } while (peek() != EOF);
  return 0;

}- Hide quoted text -

- Show quoted text -

Thanks for this. Looks like you stole my approach, but I find that
most gratifying if true, and an indication that "great minds think
alike" if not. Your contribution at a minimum is to show just how
gnomic and terse one can be in C. It would not be appropriate to
credit me since it is a common and solid algorithm that has been
around for years.

Hope you don't mind, but I'm going to copy this code and incorporate
it in what will not be a three way test: of my C Sharp version, my C
version and your gnomic C. I want to add more testing (using a random
generator in C Sharp), a GUI and timing comparisions and shall report
back.- Hide quoted text -

This doesn't qualify as anything like theft or great thinking. For
fun, I wrote the code in about 5 minutes after the OP posted (based on
http://groups.google.com/group/comp.lang.c/msg/fe772c9d6a28fdc4), but
refrained from posting it because it was probably homework for the
OP. This is a standard example or homework assignment for just about
any undergrad course that covers recursive descent parsing. The
gramamr with minor variations is in at least a dozen complier design
textbooks including ASU. Usually it's given in left-recursive form,
and then the author or student go through the L-rec removal, left-
factoring, and BNF conversion. RPN generation is a trivial example of
attribute evaluation.

 

[Seebs]

Am I interpreting spinoza1111's remark here correctly? It also
seems he is slighting programmers who work on embedded systems. I
suppose this shouldn't be surprising, but it's just so painfully
absurd. The many contributions of embedded systems programmers (I'm
not one, but do admire them) are demonstrably undeniable.

You forgot! I mentioned at one point that my dayjob involves embedded
software. I do it, therefore it's horrible in his world.

Like the way that, the moment he found out I hadn't done any CS classes,
the people attacking Schildt went from being over-educated fools without
real-world experience to uneducated and therefore unqualified. I'm half
tempted to go take a CS class just to make him flip-flop again.

-s

 

[Seebs]

This post contains the promised C code version of the infix to Polish
notation convertor. When run from the command line it should execute
all cases used to test the C Sharp version correctly. Its string
handling is simpler owing to the limitations of C.
Okay.

#include <stdio.H>
#include <stdlib.H>

Don't capitalize the "H" -- while it may happen to work on your system,
it means the code won't compile on others. Even an easily-fixed compile
error makes people likely to discount your code.

#define MAX_POLISH_LENGTH 100

int errorHandler(char *strMessage)
{
printf("\n%s\n", strMessage); return 0;
}

This always returns the same value, why does it have a return value at
all?

If this is for an error message, why isn't it using stderr for its output?

The double-\n thing is a bit unusual; normally a convention is adopted
where messages should either end with (normally) or start with (less
often) a newline, rather than providing two. In particular, if there are
two consecutive error messages for some reason, this would produce a blank
line between them.

It would seem much more useful to implement this function using ... arguments
and the underlying vfprintf() to allow formatted messages to be displayed.
If I were writing a function to this effect, I'd probably do:

void
errorHandler(char *msg, ...) {
va_list ap;
va_start(ap, fmt);
vfprintf(stderr, fmt, ap);
va_end(ap);
}

You prefix the variable's name with a type. While that certainly CAN be
a reasonable thing, it's important to ensure that the type used is a real
abstract type, not merely a language type -- language types are already
type checked.

int errorHandlerSyntax(int intIndex, char *strMessage)

You're using Systems Hungarian here, which is crap. Don't. Apps Hungarian
is what Simonyi proposed and demonstrated to be useful. Systems Hungarian
isn't useful, and leads to bugs later.

{
printf("\nError at character %d: %s\n",
intIndex,
strMessage);
return 0;
}

This is a useless message. It doesn't tell the user what the character
IS, nor does it give the user any feedback as to the nature of the message.
And, again, suggest that you implement format arguments.

int stringLength(char *strInstring)
{
int intIndex1;
for (intIndex1 = 0;
strInstring[intIndex1] != '\0';
intIndex1++) { }
return intIndex1;
}

Why the **** did you even write this? strlen() exists for a reason.
And just for extra credit: This name is reserved for use exclusively
by the implementation, since it starts with "str" followed by a lowercase
letter. In practice it's likely harmless in modern systems because
names are usually case-sensitive, and the standard doesn't define library
functions with camelCase.

But it's still stupid.

int stringAppendChar(char *strInstring,
char chrNew,
int intMaxLength)
{
int intLength = stringLength(strInstring);
if (intLength >= intMaxLength - 1)
{
errorHandler
("Cannot append character: string too long");
return 0;
}
strInstring[intLength] = chrNew;
strInstring[intLength + 1] = '\0';
return -1;
}

int
stringAppendChar(char *s, char c, size_t max) {
char *end = strchr(s, '\0');
if (end - s < max) {
*end++ = c;
*end = '\0';
return end - s;
} else {
return -1;
}
}

Note that I've changed the sense of the return value. This is because
by convention -1 indicates a failure. Returning the actual length,
rather than a meaningless value, gives the caller some additional
information.

Note that I've preserved the probable-bug, which is that if you have an
array of 15 characters, and you call this function with the limit 15 on
an array containing 14 non-zero characters and a null byte,
it'll write the 16th character of the 15-character array. That's almost
always a bad choice.

I've omitted the ridiculous error message call, for reasons which shall
become apparent.

int appendPolish(char *strPolish, char chrNext)
{
return
((*strPolish == '\0' || *strPolish == ' ')
?
-1
:
stringAppendChar(strPolish,
' ',
MAX_POLISH_LENGTH))
&&
stringAppendChar(strPolish,
chrNext,
MAX_POLISH_LENGTH)
&&
stringAppendChar(strPolish, ' ', MAX_POLISH_LENGTH);
}

This is just plain horrid. The layout is surreal, and the logic
opaque.

I think you mean:

int appendPolish(char *strPolish, char chrNext)
{
if (*strPolish == ' ' || *strPolish == '\0')
return -1;
... wait, this doesn't even make sense.
}

This function aborts if the FIRST character of strPolish is a space or
a null, but then appends characters off at the end of strPolish. This
makes no sense. You'll have to put in some kind of explanatory comment
to justify that.

There's also the fact that calling stringAppendChar three times in a row
is stupid. Figure out how many characters are left, and if there's enough
room for three, append all three at once. Appending one or two of them
is not useful.

int mulFactor(char *strInfix,
char *strPolish,
int *intPtrIndex,
int intEnd)
{ /* mulFactor = LETTER | NUMBER | '(' expression ')' */
int intIndexStart = 0;
int intLevel = 0;
char chrNext = ' ';
int intInner;
if (*intPtrIndex > intEnd)
return errorHandlerSyntax(*intPtrIndex,
"mulFactor unavailable");

This is a crappy error message. The problem has nothing at all to do with
mulFactor. It has to do with you having, apparently, run out of room
or something. So say so; give a message like "string too long".

if (chrNext == '(')

This is the point where you should be calling a different function that
handles parenthesized expressions, IMHO.

if (!expression(strInfix,
strPolish,
&intInner,
*intPtrIndex - 2))

Ugh.

Seems like this would be a great time to refactor this more sanely. In
particular, you're having the higher-level code (mulfactor) try to guess
the range of the substring.

What happens when someone asks you to support strings? Then suddenly
mulfactor() has to be smart enough to find the end of:
(a + ")")

and you're making a ton of work. Wrong. When you see the (, pass it off
to the function which tries to find an expression followed by a trailing ),
and have the expression parser hand what it found so far back up when it
sees the ) -- at which point the parens function finds its trailing ) and is
happy.

char *infix2Polish(char *strInfix)
{
int intIndex = 0;
char *strPolish = malloc(MAX_POLISH_LENGTH);

Sure enough, you did what I thought you'd do. You allocate MAX_POLISH_LENGTH
characters, but then, you use MAX_POLISH_LENGTH as the cap you pass to
strAppendChar, meaning that if your Polish string contains MAX_POLISH_LENGTH-1
characters, you will end up writing one past the end of the array.

It turns out that the fencepost conventions people use in C are there for
a good reason.

if (strPolish == 0)
errorHandler("Can't get storage");
strPolish[0] = '\0';

Since errorHandler doesn't exit in any way, you're still going to segfault
(or whatever) when you reach this line.

if (!expression(strInfix,
strPolish,
&intIndex,
stringLength(strInfix) - 1))
{
errorHandler("Can't parse expression");
return "";

Oh, that's great. You are now returning pointers from this function which
MAY OR MAY NOT be the results of malloc(), so you can't free them safely.

This should be:
strPolish[0] = '\0';
return strPolish;

printf("Expect 10 113 + a *: %s\n",
infix2Polish("(10+113)*a"));

Because infix2Polish allocates memory, but you never free the results, this
is a memory leak.

int main(int intArgCount, char **strArgs)

Renaming the args to main, not useful. Declaring them when you're not using
them, also not useful.

{
tester();
return;

return without a value in function not returning void

Okay, I will concede one point: You would actually be better off reading
Schildt's books than muddling along without. You'd be even better off reading
a better C book, but really, any port in a storm.

-s

 

[Seebs]

It really makes the regs (and, most especially, the reg-wannabees like
Mr. Streater here) nervous to be seen as in any way requesting anything
(other than order-in-the-court, of course). That is, it destroys their
game to be seen as being in the position of asking for something as
opposed to always being the givers of knowledge.

.... Wow, you're really committed to this idea that your social instincts
are the way everyone else in the world works, exactly.

Sure must be cool being a member of a species with absolutely NO variance
in cognitive experience. Over here on my planet, see, different people aren't
all the same, so some people might value different things than others.

In fact, I ask people for stuff all the time, and I have no problems admitting
that I need a lot of help from people to get by much of the time. Fine by
me. I'm not the one with a crippling ego problem.

Notice the recent hoo-hah about whether or not Kiki/RH had requested
anything from Jacob. Notice how much virtual ink was expended
discussing what was, in fact, just a small, jocular, off-the-cuff remark
from Jacob.

I don't tihnk I'd call it "jocular".

Kiki was obviously much distressed by both of the following
implications, and spared no effort to try to dispel both:

I used to watch arguments between people who were firmly convinced that
it would persuade people that evolution never happened if Darwin had
recanted, and people who didn't actually care what Darwin thought. The
thing is, the latter people didn't care what Darwin thought because they
were pure empiricists; they thought statements were true if supported
by evidence, and false if not supported by evidence.

The thing is, the evidence suggests that Darwin didn't recant. So,
being much concerned with evidence, they pointed this out... And the
people who thought it was all about authority figures interpreted this,
not as an argument over facts, but as an attempt to defend the authority
of the figure.

You're doing the same thing.

1) That they (Kiki and/or RH) had requested something from lowly Jacob.

I have requested things from Jacob. I disagree with him strongly on some
issues, but I reject categorically the notion that he is "lowly". He's an
implementor who is, to the best of my knowledge, *single-handedly* maintaining
a C compiler. I would state without fear of contradiction that there are
aspects of C compiler development and maintenance which he knows much better
than I do. (And my day job is, specifically, compiler maintenance and
support. The difference is, I'm just a gopher between our customers and
our toolchain vendor.)

2) That, in response to and in fulfillment of said request, Jacob
had actually, out of the goodness of his heart, produced something
of value.

I do not believe that such a request occurred. I wouldn't have made one
because I am not in Jacob's target market (I don't use Windows much). But
I would never deny that Jacob produced something of value. If I found
myself obliged to use Windows systems much, I am confident that Jacob's
compiler would be useful to me, and I'd certainly prefer it to whatever
I could get from Microsoft.

Now, the great thing is: I pointed these things out because I'm obsessive
about factual accuracy, and you're going to reinterpret them in terms of
status. The difference being, I can conceive of people using other values
than I have. You apparently still can't.

-s

 

[Seebs]

Yowza. I can see that would have created a stir. Along that vein of
thought, I'm amazed that they tolerate Keighley aiding and abetting
them recently - almost as if he had his own seat at the high table.

If you're amazed by something, that's often a sign that you have a faulty
premise.

Hint: There is no "high table". I don't recognize peoples' names very
much, and I don't much care who's who.

-s