算法4的语言载体是Java,所以书上算法的实现是以Java语言形式来的。一个非常经典的算法，在这里把他以C++重写一遍，加深印象的同时给广大网友一个参考。

问题描述:

求形如 (1*((2+3)*(4*5)))的算术表达式。

这里运算的优先级都用挎号提现出来了，所以也降低了算法的实现难度。

 

算法思想：

这里定义两个栈，一个栈用来存操作数(aux),另一个栈用来存运算符(ope)

具体步骤:

1.将操作数压入操作数栈；

2.将运算符压入运算符栈；

3.忽略左括号;

4.在遇到右括号得时候弹出一个运算符，弹出所需数量得操作数，并将运算符和操作数的运算结果压入操作数栈。

在处理完最后一个右括号之后，操作数栈上只会有一个值，就是计算结果。

下面给出栈的设计以及测试用例:

栈的设计

#include
     
      using namespace std;template 
      
        //栈的模板类定义class MyStack {private:    vector
       
         data;    int ret;    int size;public:    MyStack();       //构造函数    void push(Type x);//压栈操作    bool isEmpty();   //判断栈是否为空    Type pop();       //出栈操作    int FetchSize() { return data.size }; //获取栈的大小};template 
        
         MyStack
         
          ::MyStack(){    ret = 0;    size = 0;}template 
          
           void MyStack
           
            ::push(Type x) { data.push_back(x);}template 
            
             bool MyStack
             
              ::isEmpty() { return data.empty();}template 
              
               Type MyStack
               
                ::pop() { if (isEmpty()) { return false; } ret = data.back(); data.pop_back(); return ret;}
               
              
             
            
           
          
         
        
       
      
     

算法实现

#include
     
      #include
      
        #include
       
        #include "Stack.h"#include
        
         using namespace std;int main(){    MyStack
         
           ops = MyStack
          
           (); //定义运算符栈 MyStack
           
             vals = MyStack
            
             ();//定义操作数栈 string operation; cin >> operation; for (char s:operation) { if (s == '('); else if (s == '+'|| s == '-'|| s == '*'|| s == '/'|| s == 'sqrt') ops.push(s); else if (s == ')') { char op = ops.pop(); double v = vals.pop(); if (op == '+') v = vals.pop() + v; else if (op == '-') v = vals.pop() - v; else if (op == '*') v = vals.pop() * v; else if (op == '/') v = vals.pop() / v; else if (op == 'sqrt') v = sqrt(v); vals.push(v); } else { double d = (int)(s-48); vals.push(d); } } int result = vals.pop(); cout << result << endl; return 0;}