[C++知识库]C++对表达式进行求值计算

1.首先我们需要成立两个栈，一个用来存放操作数(intStack)，一个用来存放运算符(charStack)

2.对输入的表达式进行扫描

如果抽取的操作数，则压入intStack中

如果抽取的是'+'或者’-‘运算符，则处理charStack栈顶相等或更高优先级的运算符，然后将运算符压入charStack中

如果抽取到的是'*'或者'/'运算符，则处理charStack栈顶相等的优先级的运算符，然后将运算符压入栈中

如果抽到的是'('，则直接压入栈中

如果抽到的是')'，则重复处理charStack栈顶中所有运算符直到遇到'('

3.重复处理charStack栈顶运算符直到栈为空

#ifndef ImprovedStack_hpp
#define ImprovedStack_hpp

#include <stdio.h>
template<typename T>
class Stack{
public:
    Stack();
    Stack(const Stack&);
    ~Stack();
    bool empty();
    T peek();
    void push(T value);
    T pop();
    int getSize();
private:
    T* elements;
    int size;
    int capacity;
    void ensureCapacity();
};

template<typename T>
Stack<T>::Stack(){
    size = 0;
    capacity = 16;
    elements =new T[capacity];
}
template<typename T>
Stack<T>::Stack(const Stack& stack){
    elements = new T[stack.capacity];
    size = stack.size;
    capacity = stack.capacity;
    for (int i= 0; i<size; i++) {
        elements[i] = stack.elements[i];
    }
}
template<typename T>
Stack<T>::~Stack(){
    delete [] elements;
}
template<typename T>
bool Stack<T>::empty(){
    return size == 0;
}
template<typename T>
T Stack<T>::peek(){
    return elements[size-1];
}
template<typename T>
void Stack<T>::push(T value){
    ensureCapacity();
    elements[size++] = value;
}
template<typename T>
T Stack<T>::pop(){
    return elements[--size];
}
template<typename T>
int Stack<T>::getSize(){
    return size;
}
template<typename T>
void Stack<T>::ensureCapacity(){
    if (size >= capacity) {
        T* old =elements;
        capacity = 2*size;
        elements = new T[size*2];
        for(int i = 0;i<size;i++){
            elements[i] =old[i];
        }
        delete [] old;
    }
}

#endif /* ImprovedStack_hpp */

#include <iostream>
#include <string>
#include <vector>
#include <cctype>
#include "ImprovedStack.hpp"
using namespace::std;
//将输入的表达式分割为数字，运算符，括号
vector<string> split(const string& expression);
//计算表达式结果
int evaluateExpression(const string& expression);
//操作数栈和运算符栈
void processAnOperator(Stack<int>& intStack, Stack<char>& charStack);

int main(int argc, const char * argv[]) {
    // insert code here...
    string expression;
    cout<<"请输入一串表达式:"<<endl;
    getline(cin, expression);
    cout<<expression<<"="<<evaluateExpression(expression)<<endl;
    return 0;
}
vector<string> split(const string& expression){
    vector<string> v;
    string numberString;
    for (unsigned i=0; i<expression.length(); i++) {
        if (isdigit(expression[i])) {
            numberString.append(1,expression[i]);
        }
        else{
            if (numberString.size()>0) {
                v.push_back(numberString);
                numberString.clear();
            }
            if (! isspace(expression[i])) {
                string s;
                s.append(1,expression[i]);
                v.push_back(s);
            }
        }
    }
    if (numberString.size()>0) {
        v.push_back(numberString);
    }
    return v;
}
int evaluateExpression(const string& expression){
    Stack<int> intStack;
    Stack<char> charStack;
    vector<string> token = split(expression);
    for(unsigned i=0;i<token.size();i++) {
        if (token[i][0] == '+' || token[i][0] =='-') {
            while (!charStack.empty()&&
                   (charStack.peek()=='+'||
                    charStack.peek()=='-'||
                    charStack.peek()=='*'||
                    charStack.peek()=='/')) {
                processAnOperator(intStack, charStack);
            }
            charStack.push(token[i][0]);
        }
        
        else if (token[i][0]=='*'||token[i][0]=='/'){
            while (!charStack.empty()&&
                   (charStack.peek()=='*'||
                    charStack.peek()=='/')) {
                    processAnOperator(intStack, charStack);
            }
                    charStack.push(token[i][0]);
        }
                    
        else if(token[i][0]=='('){
                charStack.push(token[i][0]);
        }
                    
        else if(token[i][0]==')'){
                while(charStack.peek()!='('){
                    processAnOperator(intStack, charStack);
            }
                charStack.pop();
        }
                    
        else{
                intStack.push(atoi(token[i].c_str()));
        }
    }
                    
    while(!charStack.empty()){
                processAnOperator(intStack,charStack);
    }
    return intStack.pop();
}
void processAnOperator(Stack<int>& intStack, Stack<char>& charStack){
    char op = charStack.pop();
    int op1 =  intStack.pop();
    int op2 =  intStack.pop();
    if (op =='+') {
        intStack.push(op2 + op1);
    }
    else if (op == '-'){
        intStack.push(op2 - op1);
    }
    else if (op == '*'){
        intStack.push(op2 * op1);
    }
    else if (op == '/'){
        intStack.push(op2 / op1);
    }
}