Write a program to evaluate a postfix expression. You only have to handle four kinds of operators: +, -, x, and /. Format of functions: ElementType EvalPostfix( char *expr ); where expr points to a string that stores the postfix expression. It is guaranteed that there is exactly one space between any two operators or operands. The function EvalPostfix is supposed to return the value of the expression. If it is not a legal postfix expression, EvalPostfix must return a special value Infinity which is defined by the judge program.
时间: 2024-02-04 16:04:19 浏览: 82
Sure, I can help you with that. Here's the implementation of the `EvalPostfix` function in C:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#define Infinity 1e9 // special value for invalid expression
typedef double ElementType; // type of operands
typedef struct Stack {
int top; // index of the top element
int capacity; // max capacity of the stack
ElementType *array; // array to store elements
} Stack;
// function to create a new stack
Stack *CreateStack(int capacity) {
Stack *stack = (Stack *) malloc(sizeof(Stack));
stack->top = -1;
stack->capacity = capacity;
stack->array = (ElementType *) malloc(stack->capacity * sizeof(ElementType));
return stack;
}
// function to check if the stack is empty
bool IsEmpty(Stack *stack) {
return stack->top == -1;
}
// function to check if the stack is full
bool IsFull(Stack *stack) {
return stack->top == stack->capacity - 1;
}
// function to push an element onto the stack
void Push(Stack *stack, ElementType element) {
if (IsFull(stack)) {
printf("Error: Stack is full\n");
exit(EXIT_FAILURE);
}
stack->array[++stack->top] = element;
}
// function to pop an element from the stack
ElementType Pop(Stack *stack) {
if (IsEmpty(stack)) {
printf("Error: Stack is empty\n");
exit(EXIT_FAILURE);
}
return stack->array[stack->top--];
}
// function to evaluate a postfix expression
ElementType EvalPostfix(char *expr) {
Stack *stack = CreateStack(strlen(expr));
char *token = strtok(expr, " "); // get the first token
while (token != NULL) {
if (isdigit(token[0])) { // if token is an operand
Push(stack, atof(token)); // push it onto the stack
} else { // if token is an operator
// pop the top two elements from the stack
ElementType operand2 = Pop(stack);
ElementType operand1 = Pop(stack);
// perform the operation and push the result onto the stack
switch (token[0]) {
case '+':
Push(stack, operand1 + operand2);
break;
case '-':
Push(stack, operand1 - operand2);
break;
case 'x':
Push(stack, operand1 * operand2);
break;
case '/':
if (operand2 == 0) { // division by zero
return Infinity;
}
Push(stack, operand1 / operand2);
break;
default:
return Infinity; // invalid operator
}
}
token = strtok(NULL, " "); // get the next token
}
if (stack->top != 0) { // invalid expression
return Infinity;
}
return Pop(stack); // return the final result
}
int main() {
char expr[] = "5 3 2 x - 4 +";
ElementType result = EvalPostfix(expr);
if (result == Infinity) {
printf("Error: Invalid expression\n");
} else {
printf("Result = %g\n", result);
}
return 0;
}
```
In this implementation, we use a stack to store the operands and perform the operations on them. We tokenize the postfix expression using the `strtok` function and process each token one by one. If the token is an operand, we convert it to a `double` and push it onto the stack. If the token is an operator, we pop the top two elements from the stack, perform the operation, and push the result back onto the stack. If the expression is invalid, we return the special value `Infinity`.
阅读全文