Преобразование и оценка инфикса в постфикс, включая пробелы и двойные кавычки

Question

У меня есть код ниже, но мне нужен код для учета пробелов и двойных цифр, например, если я введу (7-3) / (2 + 2), он должен получиться 73-22 + / результат: 1. Если я введу (7 - 3) / (2 + 2), он должен выйти 7 3 - 2 2 + / результат 1. Если я введу (22 - 10) / (2 + 2), он должен выйти 22 10 - 2 2 + / Результат: 3

Вот код, который у меня есть:

#include<stdio.h>
char stack[100];
int top = 0;
int eval_top = -1;
int eval_stack[100];

void push(char x) // Push char into stack
{
  stack[top++] = x;
}
char pop() // Pop char to top of stack
{
  if (top == -1)
    return -1;
  else
    return stack[top--];
}

/* functions for evaluation of postfix expression */
// push function
void eval_push(int x) { // Find push result
  eval_stack[++eval_top] = x;
}
// pop function
int eval_pop() { // Find pop result
  if (eval_top == -1) {
    return -1;
  } else {
    return eval_stack[eval_top--];
  }
}

int priority(char x) // check priority order
{
  if (x == '(')
    return 0;
  if (x == '+' || x == '-')
    return 1;
  if (x == '*' || x == '/')
    return 2;
}
// function to evaluate the postfix expression
void EvalPostfix(char postfix[]) {

  int A, B;
  int val;
  char ch;
  int i;

  //find postfix
  for (i = 0; postfix[i] != ')'; i++) {
    ch = postfix[i];
    if (isdigit(ch)) {
      eval_push(ch - '0');
    } else if (ch == '+' || ch == '-' || ch == '*' || ch == '/') {

      A = eval_pop();
      B = eval_pop();

      switch (ch) {
      case '*':
        val = B * A;
        break;

      case '/':
        val = B / A;
        break;

      case '+':
        val = B + A;
        break;

      case '-':
        val = B - A;
        break;
      }

      eval_push(val); //send value on top of stack
    }
  }
  printf("\n Result: %d \n", eval_pop());
}

main() {
  int i = 0;
  char * e, x;
  char postfix[100]; // store postfix for later evaluation
  char exp[100];
  printf("Infix expression : ");
  scanf("%s", exp); // asking the user to enter the infix expression
  printf("Postfix expression: ");
  e = exp;
  while ( * e != '\0') {
    if (isalnum( * e)) { // if character is alphabet or number , it is printed
      printf("%c", * e);
      postfix[i++] = * e;
    } else if ( * e == '(') // if it is open parenthesis, it is pushed into the stack without any priority
      push( * e);
    else if ( * e == ')') // if it is closed parenthesis , pop the elements in the stack and print them until the we see ( symbol
    {
      while ((x = pop()) != '(') {
        printf("%c", x);
        postfix[i++] = x;
      }
    } else // if character is symbol like +, -, *, / then based on their priority character is pushed if it high priority otherwise high priority symbols are popped and it is pushed
    {
      while (priority(stack[top]) >= priority( * e)) {
        x = pop();
        printf("%c", x);
        postfix[i++] = x;
      }
      push( * e);
    }
    e++;
  }
  while (top != -1) // printing remaining elements in the stack
  {
    x = pop();
    printf("%c", x);
    postfix[i++] = x;
  }
  postfix[i] = ')'; // this is to add at the end for detecting end by the evaluation function
  EvalPostfix(postfix);
}

Answer 1

В вашем коде есть некоторые проблемы

ваш pop не симметричен вашему push , push post, увеличивающему индекс, поэтому pop должен предварительно уменьшать индекс, и из-за этого первый неверный индекс не -1, а 0:

char pop() // Pop char to top of stack
{
  if (top == 0)
    return -1;
  else
    return stack[--top];
}

приоритет не возвращает значение, если все тесты являются ложными, но, вероятно, последний тест бесполезен

В

while (priority(stack[top]) >= priority( * e))

вы пропустили, чтобы проверить, пуст ли стек, должно быть:

while ((top != 0) && (priority(stack[top]) >= priority( * e))) {

Поскольку первый недопустимый индекс для стека равен 0, а не -1

while (top! = -1) // печать оставшихся элементов в стеке

должно быть

while (top != 0) // printing remaining elements in the stack

Когда вы делаете постфиксное выражение, между числами нет разделения, например, «12 + 3» становится «123+», как «1 + 23», а в EvalPostfix вы считаете, что число имеет только одна цифра (eval_push(ch - '0');), поэтому вы не можете управлять числами, имеющими более 1 цифры. Для управления несколькими цифрами добавьте разделитель после всех чисел, например, пробел, в котором должно быть "12 3+" или "1 23 +", и прочитайте число с помощью scanf и т. Д.

Вы не делаете правильное постфиксное выражение во всех случаях, например, для 1 + 2 * 3 вы делаете 12 + 3 *, но оно должно быть 123 * +

Вы не можете обнаружить недопустимые инфиксные выражения

---

в

while (priority(stack[top]) >= priority( * e))

Я пропустил, что верхний элемент не stack[top], а stack[top - 1], поэтому его нужно заменить на

while ((top != 0) && (priority(stack[top - 1]) >= priority( * e))) {

добавив, что исправление 1 + 2 * 3 приводит к правильному выражению постфикса 123 * +

Обратите внимание, что более понятно ввести функцию empty () и tops () , а в случае неправильного доступа в стек вывести сообщение и выйти, а не вернуть -1 как char

int empty()
{
   return (top == 0);
}

char tops()
{
   if (top == 0) {
     fputs("top() on the empty stack, abort", stderr);
     exit(-1);
   }
   return stack[top - 1];
}

char pop() // Pop char to top of stack
{
  if (top == 0) {
     fputs("pop() on the empty stack, abort", stderr);
     exit(-1);
  }
  return stack[--top];
}

также обнаруживает возможное переполнение стека:

void push(char x) // Push char into stack
{
  if (top == sizeof(stack)) {
    fputs("stack overflow", stderr);
    exit(-1);
  }
  stack[top++] = x;
}

так что теперь вы можете сделать

    while (!empty() && (priority(tops()) >= priority( * e))) {

Конечно, то же самое для другого стека

Мне нужен код для учета пробелов и двузначных чисел

двойные цифры слишком ограничены, просто управляйте любым целым числом, для этого вы можете извлечь число, используя strtol . Вы также не можете прочитать полное выражение, используя scanf("%s", exp);, потому что останавливается на первом пробеле, используйте fgets .