spinoza1111 said:
This post contains the promised C code version of the infix to Polish
notation convertor.
Seebs as commented on the code in detail, so I'll just add that you
need more work on some error cases. Despite a lot of unnecessary
counting of parentheses, cases like "1)" and "(((0))))" are silently
ignored.
Also, I think it would be better to try to detect all input that can't
be converted. For example, "&" gives an error, but "1&2" does not.
In order to be positive, I'll stick my neck out and post my solution.
No one has posted the classic operator priority parsing algorithm, so
this solution is new in the thread. The code is simpler than the code
you get from turning grammar rules directly into paring functions,
although the benefit is certainly borderline for expressions with only
two priorities. I've added an extra, high priority, operator (^) to
illustrate the algorithm's generality.
All the work heavy is done in one function (convert_operators in the
code below) that parses sequences of terms whose length is determined
by the priority of the operators that are seen. If these are
determined from a run-time table, you get the advantage of being able
to add and remove operators as well as changing the operator
precedences as the parser runs.
Most of the code is scaffolding and includes an expanding character
buffer to hold the growing output string. C99 features are used in a
couple of places.
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
/*
* This type, and the two str_ functions, provide an expanding
* character buffer to take the growing output string.
*/
typedef struct string string;
void str_add(string *s, char c);
const char *str_string(string *s);
static bool convert_term(const char **s, string *out);
static bool convert_operators(const char **s, int precedence, string *out);
static bool convert_expression(const char **s, string *out);
static char next(const char **s);
static bool expect(const char **s, char c);
static bool missing(const char *what, char where);
/*
* The grammar is largely specified by this function that determines
* if a token (in this case a single character) is an operator and,
* if so, what precedence it has.
*/
static int precedence_of(char op)
{
static const char *op_table[] = { "+-", "*/", "^", NULL };
if (op != '\0')
for (int i = 0; op_table
; i++)
if (strchr(op_table, op))
return i;
return -1; /* not a operator */
}
bool infix_to_postfix(const char *s, string *out)
{
return convert_expression(&s, out) && expect(&s, '\0');
}
static bool convert_expression(const char **s, string *out)
{
return convert_term(s, out) && convert_operators(s, 0, out);
}
static bool convert_operators(const char **s, int precedence, string *out)
{
char op;
int prec, right_prec;
while ((prec = precedence_of(op = next(s))) >= precedence) {
*s += 1;
if (convert_term(s, out))
while ((right_prec = precedence_of(next(s))) > prec) {
if (!convert_operators(s, right_prec, out))
return false;
}
else return false;
str_add(out, op);
str_add(out, ' ');
}
return true;
}
static bool convert_term(const char **s, string *out)
{
unsigned char c = next(s);
if (isalpha(c)) {
str_add(out, c);
str_add(out, ' ');
*s += 1;
return true;
}
else if (isdigit(c)) {
while (isdigit((unsigned char)**s))
str_add(out, *(*s)++);
str_add(out, ' ');
return true;
}
else if (c == '(') {
*s += 1;
return convert_expression(s, out) && expect(s, ')');
}
else return missing("Term", c);
}
static char next(const char **s)
{
while (isspace((unsigned char)**s)) *s += 1;
return **s;
}
static bool missing(const char *what, char where)
{
fprintf(stderr, "%s expected where %s found.\n", what,
where ? (char []){where, 0} : "end of input");
return false;
}
static bool expect(const char **s, char c)
{
if (next(s) != c)
return missing(c ? (char []){c, 0} : "end of input", **s);
*s += 1;
return true;
}
/*
* An implementation of an expanding character buffer.
*/
struct string {
size_t capacity, size;
char *string;
};
void str_add(string *s, char c)
{
if (s->size >= s->capacity) {
size_t new_cap = s->capacity * 3 / 2 + 8;
char *new_s = realloc(s->string, new_cap);
if (!new_s) {
fprintf(stderr, "String add: out of memory\n");
exit(EXIT_FAILURE);
}
s->string = new_s;
s->capacity = new_cap;
}
s->string[s->size++] = c;
}
const char *str_string(string *s)
{
str_add(s, '\0');
return s->string;
}
int main(int argc, char *argv[])
{
bool result = true;
while (--argc > 0) {
string postfix = {0};
if (infix_to_postfix(*++argv, &postfix))
printf("%s\n", str_string(&postfix));
else result = false;
free(postfix.string);
}
return result ? EXIT_SUCCESS : EXIT_FAILURE;
}
