用C++编写基于堆栈的一位整数中缀表达式计算器

所属类别：C/C++
文章作者：ideawu
推荐指数：★★★☆
文档人气：188
本周人气：2
发布日期：2007-6-5

/*******************************************
* file: stack_cal.cpp
* author: ideawu
* date: 2006-11-17
*******************************************/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef enum{
    Token_Error = 0,
    Token_Int = 'i',
    Token_Div = '/',
    Token_Mul = '*',
    Token_Sub = '-',
    Token_Add = '+',
    Token_Mod = '%',
    Token_Lp = '(',
    Token_Rp = ')'
}TokenType;

class Token{
public:
int type;
double value;

    Token(){
        type = Token_Error;
        value = 0;
    }
};

class ArrayStack{
private:
    char * name;
    Token *tokens;
    int size;
    int capacity;

public:
    ArrayStack(char* n){
        name = n;
        size = 0;
        capacity = 256;
        tokens = new Token[capacity];
    }

    ~ArrayStack(){
        delete[] tokens;
    }

    int getSize(){
        return size;
    }

    bool isEmpty(){
        return (size == 0);
    }

    bool isFull(){
        return (size == capacity);
    }

    void push(Token token){
        if(size < capacity){
            tokens[size ++] = token;
        }else{
        }
    }

    Token* pop(){
        if(size > 0){
            size --;
            return &tokens[size];
        }else{
            return NULL;
        }
    }

    Token* peek(){
        if(size > 0){
            return &tokens[size-1];
        }else{
            return NULL;
        }
    }

    void toString(){
        if(size == 0){
            printf("%s[0]=\n", name);
            return;
        }
        printf("%s[%d]=", name, size);
        printf("(");
        printf("{%c,%.4f}", tokens[0].type, tokens[0].value);
        for(int i=1; i<size; i++){
            printf(", {%c,%.4f}", tokens[i].type, tokens[i].value);
        }
        printf(")\n");
    }
};

/*
* 归约函数, 从操作数栈和操作符栈各弹出一个元素,
* 与操作数栈顶的元素(并未弹出)运算后, 结果存在操作栈顶的元素中.
*/
void calculate(ArrayStack &operandStack, ArrayStack &operatorStack){
    if(operandStack.getSize() < 2){
        return;
    }
    Token *t1 = operandStack.pop();
    Token *t2 = operandStack.peek();
    Token *op = operatorStack.pop();
    switch(op->type){
        case '*':
            t2->value *= t1->value;
            break;
        case '/':
            t2->value /= t1->value;
            break;
        case '+':
            t2->value += t1->value;
            break;
        case '-':
            t2->value -= t1->value;
            break;
        default:
            printf("*********Syntax Error!*********\n");
            exit(1);
            break;
    }
}

int main(int argc, char *argv[]){
    char buffer[256];
    if(argc > 1){
        strcpy(buffer, argv[1]);
    }else{
        printf("Input the statement(1-256 characters):\n");
        scanf("%s", buffer);
    }

    ArrayStack operandStack("operandStack ");
    ArrayStack operatorStack("operatorStack");
    int streamLen = strlen(buffer);
    char c;
    /*
     * 需要归约的情况:
     * 1. 当前的token是整数, 且操作符栈顶元素为'*'或'/';
     * 2. 当前的token是')';
     * 3. 当前的token是'+'或'-', 且操作符栈顶元素为'+'或'-';
     */
    for(int index=0; index<streamLen; index++){
        c = buffer[index];
        Token t;
        if(c >= '0' && c <= '9'){
            t.type = Token_Int;
            t.value = c - '0';
            operandStack.push(t);
            if(!operatorStack.isEmpty()){
                if(operatorStack.peek()->type == '*'
                        || operatorStack.peek()->type == '/'){
                    calculate(operandStack, operatorStack);
                }
            }
        }else{
            t.type = c;
            Token *temp;
            switch(c){
                case ')':
                    if(operatorStack.isEmpty()){
                        printf("*********Syntax Error!*********\n");
                        exit(0);
                    }
                    temp = operatorStack.peek();
                    if(temp->type == '('){
                        // 使(int) ==> int, 即去掉整数两边的括号后再归约.
                        operatorStack.pop();
                        calculate(operandStack, operatorStack);
                    }else{
                        calculate(operandStack, operatorStack);
                        operatorStack.pop();
                    }
                    break;
                case '-':
                case '+':
                    if(!operatorStack.isEmpty()){
                        temp = operatorStack.peek();
                        if(temp->type == '+' || temp->type == '-'){
                            calculate(operandStack, operatorStack);
                        }
                    }
                    operatorStack.push(t);
                    break;
                default:
                    operatorStack.push(t);
                    break;
            }
        }
    }
    calculate(operandStack, operatorStack);

    printf("=%f", operandStack.pop()->value);
    printf("\n");
    return 0;
}