问题描述

这里限定的简单表达式求值问题是用户输入一个包含+、-、*、/、非负浮点数和圆括号的合法算术表达式，计算该表达式的运算结果。

下面给出代码

Stack.h

#ifndef _STACK_H
#define _STACK_H

#include <stdbool.h>

#define INCREASE_SIZE 10
#define STACK_SIZE 20

typedef enum { OK = 1, ERROR = 0 } Status;

typedef struct STACK {
  unsigned int typeSize;
  char *pBase;
  char *pTop;
  int stackSize;
} Stack;

Status InitStack(Stack *pStack, unsigned int typeSize);
Status DestructAStack(Stack *pStack);
bool IsEmpty(Stack *pStack);
bool IsFull(Stack *pStack);
unsigned int LenOfStack(Stack *pStack);
Status CleanAStack(Stack *pStack);
Status IncreaseASTack(Stack *pStack);
Status PushIntoStack(Stack *pStack, const void *value);
Status PopFromStack(Stack *pStack, void *popElement);
Status GetTopOfStack(Stack *pStack, void *topElement);
#endif

Stack.c

#include <stdio.h>
#include <stdlib.h>
#include "Stack.h"



Status InitStack(Stack *pStack, unsigned int typeSize) {
  pStack->typeSize = typeSize;
  pStack->pBase = (char *)malloc(sizeof(char *) *
                                          pStack->typeSize * STACK_SIZE);
  if (pStack->pBase == NULL) {
    return ERROR;
  }
  pStack->pTop = pStack->pBase;
  pStack->stackSize = STACK_SIZE;
  return OK;
}

Status DestructAStack(Stack *pStack) {
  free(pStack->pBase);
  pStack->pBase = NULL;
  pStack->pTop = NULL;
  pStack->stackSize = 0;
  pStack->typeSize = 0;
  return OK;
}

bool IsEmpty(Stack *pStack) {
  return (pStack->pTop - pStack->pBase) / pStack->typeSize == 0;
}

bool IsFull(Stack *pStack) {
  return (pStack->pTop - pStack->pBase) / pStack->typeSize == pStack->stackSize;
}

unsigned int LenOfStack(Stack *pStack) {
  return (pStack->pTop - pStack->pBase) / pStack->typeSize;
}

Status CleanAStack(Stack *pStack) {
  pStack->pTop = pStack->pBase;
  return OK;
}

Status IncreaseASTack(Stack *pStack) {
  pStack->pBase = (char *)realloc(
      pStack->pBase,
      sizeof(char *) * pStack->typeSize * INCREASE_SIZE);
  if (pStack->pBase == NULL) {
    return ERROR;
  }
  pStack->pTop = pStack->pBase + pStack->stackSize * pStack->typeSize;
  pStack->stackSize += INCREASE_SIZE;
  return OK;
}

Status PushIntoStack(Stack *pStack, const void *value) {
  int i;
  char *e = (char *)value;
  if (IsFull(pStack)) {
    IncreaseASTack(pStack);
  }
  for (i = 0; i < pStack->typeSize; i++) {
    pStack->pTop[i] = e[i];
  }
  pStack->pTop += pStack->typeSize;
  return OK;
}

Status PopFromStack(Stack *pStack, void *popElement) {
  int i;
  char *e = (char *)popElement;
  if (IsEmpty(pStack)) {
    return ERROR;
  }
  pStack->pTop-=pStack->typeSize;
  for (i = 0; i < pStack->typeSize;i++){
    e[i] = pStack->pTop[i];
  }
  return OK;
}

Status GetTopOfStack(Stack *pStack, void *topElement){
  int i;
  char *e = (char *)topElement;
  if (IsEmpty(pStack)) {
    return ERROR;
  }
  pStack->pTop-=pStack->typeSize;
  for (i = 0; i < pStack->typeSize;i++){
    e[i] = pStack->pTop[i];
  }
  pStack->pTop += pStack->typeSize;
  return OK;
}

Calculator.h

#ifndef CALCULATOR_H
#define CALCULATOR_H
#define M 100

float BasicCalculate(float unit1, char operator, float unit2);
float Calculate(char *str);
#endif

Calculator.c

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>
#include "Stack.h"

float BasicCalculate(float unit1, char operator, float unit2){
    float sum = 0;
    switch(operator){
        case '+':
            sum = unit1 + unit2;
            break;
        case '-':
            sum = unit1 - unit2;
            break;
        case '*':
            sum = unit1 * unit2;
            break;
        case '/':
            if(unit2==0){
                printf("Wrong!The divisor can`t be zero!\n");
                exit(1);
            }
            sum = unit1 / unit2;
            break;
    }
    return sum;
}

float Calculate(char *str){
    char e;
    float unit1, unit2,tempSum,sum=0;
    Stack val,oper;
    InitStack(&val, sizeof(float));
    InitStack(&oper, sizeof(char));
    while(str!=NULL&&*str!='\0'){
    /*极其细微的错误，如果写出*str!='\0'&&str!=NULL则对于纯数字表达式出错。
    错误出自strpbrk函数，如果str指向NULL，则*str是错误的行为。*/
        switch(*str){
            case '(':
                PushIntoStack(&oper, str);
                str++;
                break;
            case ')':
                while(PopFromStack(&oper, &e),e!='('){
                    PopFromStack(&val, &unit2);
                    PopFromStack(&val, &unit1);
                    tempSum = BasicCalculate(unit1, e, unit2);
                    PushIntoStack(&val, &tempSum);
                }
                str++;
                break;
            case '+':
            case '-':
                while(!IsEmpty(&oper)){
                    GetTopOfStack(&oper, &e);
                    if(e!='('){
                        PopFromStack(&val, &unit2);
                        PopFromStack(&val, &unit1);
                        tempSum = BasicCalculate(unit1, e, unit2);
                        PushIntoStack(&val, &tempSum);
                        PopFromStack(&oper, &e);
                    }
                    else{
                        break;
                    }
                    PushIntoStack(&oper, str);
                    str++;
                    break;
                }
            case '*':
            case '/':
                while(!IsEmpty(&oper)){
                    GetTopOfStack(&oper, &e);
                    if(e=='*'||e=='/'){
                        PopFromStack(&val, &unit2);
                        PopFromStack(&val, &unit1);
                        tempSum = BasicCalculate(unit1, e, unit2);
                        PushIntoStack(&val, &tempSum);
                        PopFromStack(&oper, &e);
                    }
                    else{
                        break;
                    }
                }
                 PushIntoStack(&oper, str);
                str++;
                break;
            default:
                if(isdigit(*str)){
                    sscanf(str, "%f", &tempSum);
                    PushIntoStack(&val, &tempSum);
                    str = strpbrk(str, "+-*/()");
                }
        }
    }
    while(!IsEmpty(&oper)){
        PopFromStack(&oper, &e);
        PopFromStack(&val, &unit2);
        PopFromStack(&val, &unit1);
        tempSum = BasicCalculate(unit1, e, unit2);
        PushIntoStack(&val, &tempSum);
    }
    DestructAStack(&oper);
    while (!IsEmpty(&val)){
        PopFromStack(&val, &tempSum);
        sum += tempSum;
    }
    DestructAStack(&val);
    return sum;
}

main.c

#include <stdio.h>
#include <string.h>
#include "Calculator.h"

int main(void){
    char formula[M + 1];
    float sum;
    memset(formula, '\0',sizeof(formula));
    printf("Please enter a formula: ");
    scanf("%s", formula);
    sum = Calculate(formula);
    printf("The final result is: %g", sum);
    return 0;
}

运行结果

运行结果1 运行结果2