即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

数据结构栈实现四则运算

编程语言 qq_32635069 29℃ 0评论
例如,计算9+(3-1)*3+8/2

思路:通过栈来实现上述元素,我们一般称上述表达式为中缀表达式,我们首先要将其转换为后缀表达式,因为中缀表达式不利于计算机运算。

上代码:


算法思路:


对字符串中的内容,遇到数字就输出,遇到符号则与栈顶元素比较优先级,若低,则将栈顶元素弹栈,若高,则压栈。若为右括号,则连续输出,直到遇到左括号,这输出的就是后缀表达式


其中isp()和icp()这两个函数是对于优先级的规定,在下一段代码中有它们的定义

void postfix(){
    stack<char> s;
    char y;
   // s.makeEmpty();
    s.push('#');
    char ch[20]="9+(3-1)*3+8/2"; 
    for(int i=0;i<13;i++){
        if(isdigit(ch[i]))
            cout<else if(ch[i]==')'){
          //  cout<
            while(!(s.empty())&&(y=s.top())!='('){
                cout<if(!s.empty())
                s.pop();
        }
        else{
            while(!s.empty()&&isp(y=s.top())>icp(ch[i])){
                cout<while(!s.empty()){
        cout<

有了后缀表达式,我们需要的是计算,我们做的是,遇数字压栈,与符号则弹出前两个数进行计算,将结果入栈。

#include
#include
#include
using namespace std;
int isp(char ch){
    switch(ch){
        case '#':
            return 0;
        case '(':
            return 1;
        case '^':
            return 7;
        case '*':
        case '/':
        case '%':
            return 5;
        case '+':
        case '-':
            return 3;
        case ')':
            return 8;
    }
}
int icp(char ch){
    switch(ch){
        case '#':
            return 0;
        case '(':
            return 8;
        case '^':
            return 6;
        case '*':
        case '/':
        case '%':
            return 4;
        case '+':
        case '-':
            return 3;
        case ')':
            return 1;
    }
}

class Calculator{
public:
    Calculator(){}
    double Run();
    void Clear();
private:
    void AddOperand(double value);
    bool Get2Operands(double &left,double &right);
    void DoOperator(char op);
    stack<double> s;
};
void Calculator::AddOperand(double value){
    s.push(value);
}
void Calculator::Clear(){

}
bool Calculator::Get2Operands(double &left,double &right){
    if(s.empty()){
        cerr<<"Missing Operands!"<return false;
    }
    right = s.top();
    s.pop();
    if(s.empty()){
        cerr<<"Missing Operands!"<return false;
    }
    left = s.top();
    s.pop();
    return true;
}
void Calculator::DoOperator(char op){
    double left,right;
    bool result;
    result = Get2Operands(left,right);
    if(result==true){
        switch(op){
            case '+':
                s.push(left+right);
                break;
            case '-':
                s.push(left-right);
                break;
            case '*':
                s.push(left*right);
                break;
            case '/':
                if(abs(right)<=1E-6){
                    cerr<<"Divide By 0"<else
                    s.push(left/right);
                break;
         /*   case '^':
                s.push(left^right);
                break;*/
        }
    }
    else{
        Clear();
    }
}
double Calculator::Run(){
    char ch;
    double newoperand,ret;
    while(cin>>ch,ch!='='){
        switch( ch ) {
          case '+':
          case '-':
          case '*':
          case '/':
          case '^':
              DoOperator(ch);
              break;
          default:
              cin.putback(ch);
              cin >> newoperand;
              AddOperand(newoperand);
              break;
        }
    }
    ret = s.top();
    s.pop();
    return ret;
}

int main(){

   // postfix();
   Calculator c;
   double ans = c.Run();
   cout<return 0;
}

转载请注明:CodingBlog » 数据结构栈实现四则运算

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情