整体思路是逆波兰+计算后缀表达式
其中比较特殊的地方是实现了单元与多元函数的计算
首先是新引入了一个栈来存储函数名，然后在右括号的结算后把函数名push进目标栈
多元函数的逗号’,‘处理类似右括号’)’，只是不将右括号’)'从临时栈中出栈
运行截图
#include <stdio.h>#include <math.h>#include "simpio.h"#include "strlib.h"#include "stack.h"#define MaxLineLength 1000#define MaxOperatorLength 50#define MaxArrayLength 1000#define ReverseNotationOutput 1 //whether output the Reverse Polish Notation or notstring AimArray[MaxArrayLength]; //the Reverse Polish Notation array int AimSize; int priority(string x)//return the priority rank of x{if (StringEqual(x, "+") || StringEqual(x, "-")) return 1;if (StringEqual(x, "*") || StringEqual(x, "/")) return 2;return 0;}int IsSymbol(char ch)//tell whether ch is symbol(+-*/) or not{return (ch == '+' || ch == '-' || ch == '*' || ch == '/');}int IsNum(char ch)//tell whether ch is number or not{return (ch <= '9' && ch >= '0' || ch == '.');}int IsDouble(string str)//tell whether str could be converted to double or not{double result;char dummy;return (sscanf(str, " %lg %c", &result, &dummy) == 1);}int IsChar(char ch)//tell whether ch is character or not{return ((ch>='a' && ch<='z') || (ch>='A' && ch<='Z'));}int IsSeparator(char ch)//tell whether ch is separator or not{return (ch == ' ' || ch == '\t' || ch == '\n' || ch == '\r');}void push_string(stackADT stack, const string content)//push content of string{string s = (string)malloc(MaxOperatorLength*sizeof(char));s = CopyString(content);PushStack(stack, (void*)s);}void push_double(stackADT stack, const double content)//push content of double{double *x = (double*)malloc(sizeof(double));*x = content;PushStack(stack, (void*)x);}void push_aim(const string content)//push content to AimArray {string s = (string)malloc(MaxOperatorLength*sizeof(char));s = ConvertToUpperCase(CopyString(content));AimArray[AimSize++] = s;}void error(const char *x)//output error message and exit -1{printf("%s",x);exit(-1);}void GetReverseNotation(string Line)//Get the reverse polish notation from a mathematical expression{stackADT TempStack = NewStack();//stack to storage the symbol(+ - / * ( ) )stackADT FuncStack = NewStack();//stack to storage the function name(SIN COS TAN LOG POW)int len = StringLength(Line);int i, flag;for (i = 0, flag = 0; i < len; i++) //Convert Infix Expression to Reverse Polish Notation{flag++;char ch = IthChar(Line, i);if (IsSeparator(ch)) continue;if (IsNum(ch)){int t = i;while(i+1<len && IsNum(IthChar(Line, i+1))) i++;push_aim(SubString(Line, t, i));continue;} if (ch == '('){push_string(TempStack, "(");flag = 0;continue;} if (IsSymbol(ch)){if (flag == 1 && ch == '-') push_aim("0");while (!IsemptyStack(TempStack) && priority(CharToString(ch)) <= priority((char *)TopStack(TempStack)))push_aim((char *)PopStack(TempStack));push_string(TempStack, CharToString(ch));continue;} if (ch == ')'){while (TRUE){if (IsemptyStack(TempStack)) error("There is no corresponding '(' before ')'");if (StringEqual((char *)TopStack(TempStack), "(")){PopStack(TempStack);break;}push_aim((char *)PopStack(TempStack));}if (!IsemptyStack(FuncStack)) push_aim((string)PopStack(FuncStack));continue;}if (ch == ','){while (TRUE){if (IsemptyStack(TempStack)) error("There is no corresponding '(' before ','");if (StringEqual((char *)TopStack(TempStack), "(")){break;}push_aim((char *)PopStack(TempStack));}continue;}if (IsChar(ch)){int t = i;while(i+1<len && IsChar(IthChar(Line, i+1))) i++;push_string(FuncStack,SubString(Line, t, i));continue;}error("Illegal character detected");}if (!IsemptyStack(FuncStack)) push_aim((string)PopStack(FuncStack));while (!IsemptyStack(TempStack)){if (StringEqual((char *)TopStack(TempStack), "(")) error("There is a redundant '('");push_aim((char *)PopStack(TempStack));}if (ReverseNotationOutput){printf("The Reverse Polish Notation(n = %d): ",AimSize);for (i=0;i<AimSize;i++){string x = AimArray[i];printf("%s ",x);}printf("\n");}FreeStack(TempStack);FreeStack(FuncStack);}double CalcAnswer()//calculate the answer of the reverse polish notation{stackADT CalcStack = NewStack();int i;for (i = 0; i < AimSize; i++)//calculate the reverse polish notation{string str = AimArray[i];string sError = (string)malloc(MaxOperatorLength + 18);sprintf(sError, "There's redundant '%s'", str);if(StringLength(str) == 1 && IsSymbol(str[0])) //binary operator{if (IsemptyStack(CalcStack)) error(sError);double y = *(double*)PopStack(CalcStack);if (IsemptyStack(CalcStack)) error(sError);double x = *(double*)PopStack(CalcStack);switch(str[0]){case '+' :push_double(CalcStack, x + y);break;case '-' :push_double(CalcStack, x - y);break;case '*' :push_double(CalcStack, x * y);break;case '/':push_double(CalcStack, x / y);break;}} else if (StringEqual(str,"SIN")) //unary operator{if (IsemptyStack(CalcStack)) error(sError);double x = *(double*)PopStack(CalcStack);push_double(CalcStack, sin(x));} else if (StringEqual(str,"COS")){if (IsemptyStack(CalcStack)) error(sError);double x = *(double*)PopStack(CalcStack);push_double(CalcStack, cos(x));} else if (StringEqual(str,"TAN")){if (IsemptyStack(CalcStack)) error(sError);double x = *(double*)PopStack(CalcStack);push_double(CalcStack, tan(x));} else if (StringEqual(str,"LOG")){if (IsemptyStack(CalcStack)) error(sError);double x = *(double*)PopStack(CalcStack);push_double(CalcStack, log(x));} else if (StringEqual(str,"POW") || StringEqual(str,"POWER")){if (IsemptyStack(CalcStack)) error(sError);double y = *(double*)PopStack(CalcStack);double x = *(double*)PopStack(CalcStack);push_double(CalcStack, pow(x, y));} else //number {if (!IsDouble(str)){sprintf(sError, "Undefined function '%s'", str);error(sError);}push_double(CalcStack, StringToReal(str));}FreeBlock(sError);}double ans = *(double*)PopStack(CalcStack);FreeStack(CalcStack);return (ans);}//Main programmain(){string Line = (string)malloc(MaxLineLength*sizeof(char));while (TRUE){AimSize = 0; //Initializationprintf("Type the mathematical expression(enter or 'exit' to exit):\n");Line = GetLine();if (StringEqual(Line, "") || StringEqual(ConvertToUpperCase(Line), "EXIT")) break;GetReverseNotation(Line);double ans = CalcAnswer();printf("%s = %.4f\n\n", Line, ans); }return 0; }
include的是The Art and Science of C的教材库
simpio.c
/** File: simpio.c* Version: 3.0* Last modified on Tue Oct 4 11:24:40 1994 by eroberts* -----------------------------------------------------* This file implements the simpio.h interface.*/#include <stdio.h>#include <string.h>#include "genlib.h"#include "strlib.h"#include "simpio.h"/** Constants:* ----------* InitialBufferSize -- Initial buffer size for ReadLine*/#define InitialBufferSize 120/* Exported entries *//** Functions: GetInteger, GetLong, GetReal* ---------------------------------------* These functions first read a line and then call sscanf to* translate the number. Reading an entire line is essential to* good error recovery, because the characters after the point of* error would otherwise remain in the input buffer and confuse* subsequent input operations. The sscanf line allows white space* before and after the number but no other extraneous characters.*/int GetInteger(void){string line;int value;char termch;while (TRUE) {line = GetLine();if (line == NULL) Error("GetInteger: unexpected end of file");switch (sscanf(line, " %d %c", &value, &termch)) {case 1:FreeBlock(line);return (value);case 2:printf("Unexpected character: '%c'\n", termch);break;default:printf("Please enter an integer\n");break;}FreeBlock(line);printf("Retry: ");}}long GetLong(void){string line;long value;char termch;while (TRUE) {line = GetLine();if (line == NULL) Error("GetLong: unexpected end of file");switch (sscanf(line, " %ld %c", &value, &termch)) {case 1:FreeBlock(line);return (value);case 2:printf("Unexpected character: '%c'\n", termch);break;default:printf("Please enter an integer\n");break;}FreeBlock(line);printf("Retry: ");}}double GetReal(void){string line;double value;char termch;while (TRUE) {line = GetLine();if (line == NULL) Error("GetReal: unexpected end of file");switch (sscanf(line, " %lf %c", &value, &termch)) {case 1:FreeBlock(line);return (value);case 2:printf("Unexpected character: '%c'\n", termch);break;default:printf("Please enter a real number\n");break;}FreeBlock(line);printf("Retry: ");}}/** Function: GetLine* -----------------* This function is a simple wrapper; all the work is done by* ReadLine.*/string GetLine(void){return (ReadLine(stdin));}/** Function: ReadLine* ------------------* This function operates by reading characters from the file* into a dynamically allocated buffer. If the buffer becomes* full before the end of the line is reached, a new buffer* twice the size of the previous one is allocated.*/string ReadLine(FILE *infile){string line, nline;int n, ch, size;n = 0;size = InitialBufferSize;line = GetBlock(size + 1);while ((ch = getc(infile)) != '\n' && ch != EOF) {if (n == size) {size *= 2;nline = (string) GetBlock(size + 1);strncpy(nline, line, n);FreeBlock(line);line = nline;}line[n++] = ch;}if (n == 0 && ch == EOF) {FreeBlock(line);return (NULL);}line[n] = '\0';nline = (string) GetBlock(n + 1);strcpy(nline, line);FreeBlock(line);return (nline);}
strlib.c
/** File: strlib.c* Version: 1.0* Last modified on Fri Jul 15 14:10:41 1994 by eroberts* -----------------------------------------------------* This file implements the strlib.h interface.*//** General implementation notes:* -----------------------------* This module implements the strlib library by mapping all* functions into the appropriate calls to the ANSI <string.h>* interface. The implementations of the individual functions* are all quite simple and do not require individual comments.* For descriptions of the behavior of each function, see the* interface.*/#include <stdio.h>#include <string.h>#include <ctype.h>#include "genlib.h"#include "strlib.h"/** Constant: MaxDigits* -------------------* This constant must be larger than the maximum* number of digits that can appear in a number.*/#define MaxDigits 30/* Private function prototypes */static string CreateString(int len);/* Section 1 -- Basic string operations */string Concat(string s1, string s2){string s;int len1, len2;if (s1 == NULL || s2 == NULL) {Error("NULL string passed to Concat");}len1 = strlen(s1);len2 = strlen(s2);s = CreateString(len1 + len2);strcpy(s, s1);strcpy(s + len1, s2);return (s);}char IthChar(string s, int i){int len;if (s == NULL) Error("NULL string passed to IthChar");len = strlen(s);if (i < 0 || i > len) {Error("Index outside of string range in IthChar");}return (s[i]);}string SubString(string s, int p1, int p2){int len;string result;if (s == NULL) Error("NULL string passed to SubString");len = strlen(s);if (p1 < 0) p1 = 0;if (p2 >= len) p2 = len - 1;len = p2 - p1 + 1;if (len < 0) len = 0;result = CreateString(len);strncpy(result, s + p1, len);result[len] = '\0';return (result);}string CharToString(char ch){string result;result = CreateString(1);result[0] = ch;result[1] = '\0';return (result);}int StringLength(string s){if (s == NULL) Error("NULL string passed to StringLength");return (strlen(s));}string CopyString(string s){string newstr;if (s == NULL) Error("NULL string passed to CopyString");newstr = CreateString(strlen(s));strcpy(newstr, s);return (newstr);}/* Section 2 -- String comparison functions */bool StringEqual(string s1, string s2){if (s1 == NULL || s2 == NULL) {Error("NULL string passed to StringEqual");}return (strcmp(s1, s2) == 0);}int StringCompare(string s1, string s2){if (s1 == NULL || s2 == NULL) {Error("NULL string passed to StringCompare");}return (strcmp(s1, s2));}/* Section 3 -- Search functions */int FindChar(char ch, string text, int start){char *cptr;if (text == NULL) Error("NULL string passed to FindChar");if (start < 0) start = 0;if (start > strlen(text)) return (-1);cptr = strchr(text + start, ch);if (cptr == NULL) return (-1);return ((int) (cptr - text));}int FindString(string str, string text, int start){char *cptr;if (str == NULL) Error("NULL pattern string in FindString");if (text == NULL) Error("NULL text string in FindString");if (start < 0) start = 0;if (start > strlen(text)) return (-1);cptr = strstr(text + start, str);if (cptr == NULL) return (-1);return ((int) (cptr - text));}/* Section 4 -- Case-conversion functions */string ConvertToLowerCase(string s){string result;int i;if (s == NULL) {Error("NULL string passed to ConvertToLowerCase");}result = CreateString(strlen(s));for (i = 0; s[i] != '\0'; i++) result[i] = tolower(s[i]);result[i] = '\0';return (result);}string ConvertToUpperCase(string s){string result;int i;if (s == NULL) {Error("NULL string passed to ConvertToUpperCase");}result = CreateString(strlen(s));for (i = 0; s[i] != '\0'; i++) result[i] = toupper(s[i]);result[i] = '\0';return (result);}/* Section 5 -- Functions for converting numbers to strings */string IntegerToString(int n){char buffer[MaxDigits];sprintf(buffer, "%d", n);return (CopyString(buffer));}int StringToInteger(string s){int result;char dummy;if (s == NULL) {Error("NULL string passed to StringToInteger");}if (sscanf(s, " %d %c", &result, &dummy) != 1) {Error("StringToInteger called on illegal number %s", s);}return (result);}string RealToString(double d){char buffer[MaxDigits];sprintf(buffer, "%G", d);return (CopyString(buffer));}double StringToReal(string s){double result;char dummy;if (s == NULL) Error("NULL string passed to StringToReal");if (sscanf(s, " %lg %c", &result, &dummy) != 1) {Error("StringToReal called on illegal number %s", s);}return (result);}/* Private functions *//** Function: CreateString* Usage: s = CreateString(len);* -----------------------------* This function dynamically allocates space for a string of* len characters, leaving room for the null character at the* end.*/static string CreateString(int len){return ((string) GetBlock(len + 1));}
stack.c
/** File: stack.c* -------------* This file implements the stack.h abstraction using an array.*/#include <stdio.h>#include "genlib.h"#include "stack.h"/** Constants:* ----------* MaxStackSize -- Maximum number of elements in the queue*/#define MaxStackSize 1000/** Type: stackCDT* --------------* This type provides the concrete counterpart to the stackADT.* The representation used here consists of an array coupled with * with an integer indicating the top element of the stack. *///stackCDTÀïÃæÓиöarray struct stackCDT {void *array[MaxStackSize]; /*stack space -- pointer array*/ int top; /*top position of the stack*/};/* Exported entries *//** Function: NewStack* ------------------* This function allocates and initializes the storage for a* new stack.*/stackADT NewStack(void){stackADT stack;stack = New(stackADT);stack->top = -1;return (stack);}/** Function: FreeStack* -------------------* This function frees the stack storage.*/void FreeStack(stackADT stack){FreeBlock(stack);}/** Function: PushStack* -----------------* This function adds a new element to the top of the stack.*/void PushStack(stackADT stack, void *obj){if (stack->top == MaxStackSize-1) {Error("Pushstack called on a full stack");}stack->array[++stack->top] = obj;}/** Function: PopStack* -----------------* This function removes and returns the data value at the* top of the stack.*/void *PopStack(stackADT stack){void *result;if (stack->top == -1) {Error("Popstack of empty stack");}result = stack->array[stack->top--];return (result);}/** Function: IsemptyStack* ---------------------* This function checks if the stack is empty.*/bool IsemptyStack(stackADT stack){return (stack->top == -1);}/** Function: TopStack* -----------------* This function returns the top element of the stack.Topstack an empty stack is* an NULL pointer.*/void *TopStack(stackADT stack){void *result;if (stack->top == -1) return (NULL);result = stack->array[stack->top];return (result);}
以上
