经典问题：给出一个表达式，求其运算后的结果。

如：

思路：

首先需要将中缀表达式转化为后缀表达式
	
然后通过后缀表达式求值
第一步（中缀表达式->后缀表达式）的思路：

         定义一个操作符栈stack<char> s,一个队列queue<string>q用来存放后缀表达式，一个map用来存放运算符的优先级

         循环读取字符串的每一个字符c：

若c为'(':入栈
	
若c为')':出栈，一直出到栈顶为'(',将出栈的运算符push到q中，将'('出栈
	
若c为'+','-','*','/'其中一个，根据优先级，将优先级大于等于c的运算符出栈push到q中，然后将c入栈
	
若c为数字，则定义一个string temp = "";然后循环读取下一个字符，执行temp+=c，直到不是数字和小数点。然后将temp入队
	
执行1-4直到读取了每一个字符，然后将s中剩下的操作符push到q中，q即为所求后缀表达式
第二步（后缀表达式求值）:

        定义一个queue<string>q2 = q,一个stack<double> sd用来存放操作数

这一步很简单，从q中读取string.若第一个字符为数字，则将该string转化为double入栈
	
若第一个字符不是数字，说明是操作符，则分别定义double d1, d2,为sd的头两个操作数。然后执行这个操作符（注意d1, d2的运算顺序），将结果入栈
	
执行1-2直到q为空，此时sd只剩一个最终结果。
代码：

#include<bits/stdc++.h>
#include<queue>
using namespace std;

map<char, int>p;	//操作符优先级 
stack<char> s;		//操作符栈 
stack<double> sd;	//操作数栈，通过后缀表达式求值时需要 
queue<string> q, q2;	//后缀表达式队列

//中缀转后缀表达式 
void f(string str){
	for(int i = 0;i < str.length();i++){
		char c = str[i];
		string d = "";
		if(c == '('){								//左括号入栈
			s.push(c);
		} else if(c == ')'){						//右括号，出栈到左括号为止，并将操作符输出到后缀表达式
			while(!s.empty() && s.top() != '('){
				d += s.top();
				q.push(d);
				s.pop();
			} 
			s.pop();								//弹出左括号 
		} else if(c == '+' || c == '-' || c == '*' || c == '/'){	//如果是操作符，弹出所有优先级大于等于该运算符的栈顶元素 
			while(!s.empty() && p[s.top()] >= p[c]){				//然后将该操作符入栈 
				d += s.top();
				q.push(d);
				s.pop();
				d = "";
			} 
			s.push(c);
		} else {
			string temp = "";
			int j;
			for(j = i;j < str.length();j++){
				char t = str[j];
				if(isdigit(t) || t == '.'){
					temp += t;
				} else {
					break;
				}
			}		
			i = j - 1;
			q.push(temp);
		}
	}
	while(!s.empty()){
		string temp = "";
		temp += s.top();
		q.push(temp);
		s.pop();
	} 
} 

double to(string str){
	const char *ss = str.data();
	return atof(ss);
} 

//后缀表达式求值 
void cal(){
	while(!q2.empty()){
		string str = q2.front();
		q2.pop();
		char tt = str[0];
		if(isdigit(tt)){
			double temp = to(str);
			sd.push(temp);
		}else{
			char c = str[0];
			double t1 = sd.top();		//第二操作数 
			sd.pop();
			double t2 = sd.top();		//第一操作数 
			sd.pop();
			double num;					//结果 
			switch(c){
				case '+':
					num = t2 + t1;
					break;
				case '-':
					num = t2 - t1;
					break;
				case '*':
					num = t2 * t1;
					break;
				case '/':
					num = t2 / t1;
					break;
			}
			sd.push(num); 
		}
	} 
	cout<<sd.top();
}

int main(){
	p['+'] = p['-'] = 1;
	p['*'] = p['/'] = 2;
	string str;
	cin>>str;
	f(str);			//处理字符串 
	q2 = q;
	while(!q.empty()){
		cout<<q.front()<<" ";
		q.pop();
	}
	cout<<endl;
	cal();
}

 

表达式求值
中缀表达式求值
中缀表达式转后缀表达式
后缀表达式求值（逆波兰表达式求值）
前缀表达式（波兰表达式）

首先，大家可能不知道前缀表达式和中缀表达式，后缀表达式是什么，其有什么区别呢。我先简单介绍一下：

前缀表达式是一种没有括号的算术表达式，与中缀表达式不同的是，其将运算符写在前面，操作数写在后面。为纪念其发明者波兰数学家Jan Lukasiewicz，前缀表达式也称为“波兰式”。例如，- 1 + 2 3，它等价于1-(2+3)


中缀表达式及我们正常的式子eg:1-(2+3)


后缀表达式： 逆波兰式（Reverse Polish notation，RPN，或逆波兰记法），也叫后缀表达式（将运算符写在操作数之后）eg:1-(2+3)      1 2 3+ -

中缀表达式求值
中缀表达式即我们正常的表达式，我们先讲一下其求值规则：

1.通过一个index值（索引），来完成我们的表达式
2.如果我们发现是一个数字，就直接入数栈
3.如果我们发现是一个符号，分一下情况
3.1.如果发现当前的符号栈为空，就直接入栈
3.2.如果符号栈中有操作符，就进行比较，如果当前操作符的优先级小于或者等于栈中的操作符，就需要从数栈中pop出一个符号，进行运算，将得到的结果入数栈，然后将当前的操作符入符号栈，如果当前操作符的优先级大于栈中的操作符，就直接入符号栈。如果有括号 先将左括号入栈 碰到右括号的时候，将符号栈中栈顶元素出栈，数字栈中两次出栈顶元素，进行运算，将运算的结果插入数字栈中， 直到为右括号便停止该循坏 并移除符号栈中的左括号
4.当表达式扫描完毕，就顺序的从数栈和符号栈中pop出相应的数和符号，并进行运算。
5.最后在数栈只有一个数字，就是表达式的结果

首先我们来模拟一下：

比如：(3+4)*5-2



至此步骤结束，大家可以自己多模拟几遍。

代码：

首先我模拟了一个栈，里面添加了关于优先级的判断和是否为运算符号的判断，大家可以以只看这两种方法即可。
class ArrayStack{
    private int maxSize;//栈的大小
    private int[] stack;//数组，存放数据
    private int top=-1;//top表示栈顶，初始化为-1
    public ArrayStack(int maxSize){
        this.maxSize=maxSize;
        stack=new int[maxSize];
    }
    //栈满
    public boolean isFull(){
        return top==maxSize-1;
    }
    //栈空
    public boolean isEmpty(){
        return top==-1;
    }
    //入栈
    public void push(int data){
        if(isFull()){
            System.out.println("栈满,插入失败");
            return;
        }
        stack[++top]=data;
    }
    //出栈
    public int pop(){
        if(isEmpty()){
            System.out.println("栈空，无元素");
        return -1;
        }
        int data=stack[top];
        top--;
        return data;
    }
    //获取顶端元素
    public int peek(){
        return stack[top];
    }
    //显示栈的情况(遍历栈，从上往下)
    public void list(){
        if(isEmpty()){
            System.out.println("栈空");
            return;
        }
        for (int i = top; i >=0; i--) {
            System.out.print(stack[i]+" ");
        }
    }

    //用于判断优先级  在进行表达式运算时需要用到
    public int priority(int oper){
        if(oper=='*'||oper=='/'){
            return 1;//优先级最高
        }
        else if(oper=='+'||oper=='-'){
            return 0;
        }
        else return -1;
    }
    //判断是不是一个运算符
    public boolean isOper(char val){
        return val=='+'||val=='-'||val=='*'||val=='/'||val=='('||val==')';
    }
    //计算方法
    public int cal(int num1,int num2,int oper){
        int res=0;
        switch (oper){
            case '+':
                res=num1+num2;
                break;
            case '-':
                res=num2-num1;
                break;
            case '*':
                res=num1*num2;
                break;
            case '/':
                res=num2/num1;
                break;
             default:break;
        }
        return res;
    }
}

public class ComputerDemo {
    public static void compute(String expression){
        ArrayStack numStack=new ArrayStack(10);
        ArrayStack operStack=new ArrayStack(10);
        int index=0;
        int num1=0;//表示输出数字的栈顶元素
        int num2=0;//表示地如此输出数字栈的栈顶元素
        int oper=0;//运算符号  符号栈的栈顶元素
        int res=0;//计算结果
        char ch=' ';//将每次扫描得到的char保存到ch
        String keepNum="";//防止不止一个数字 为多位数
        //开始while循环的扫描expression
        while (index!=expression.length()) {
            //依次得到expression的每一个字符
            ch = expression.substring(index, index + 1).charAt(0);
            //判断ch是什么，然后做相应的处理
            if(operStack.isOper(ch)){
                /**
                 *  3.1.如果发现当前的符号栈为空，就直接入栈
                 *  3.2.如果符号栈中有操作符，就进行比较，如果当前操作符的
                 *    优先级小于或者等于栈中的操作符，就需要从数栈中pop出一个符号，
                 *    进行运算，将得到的结果入数栈，然后将当前的操作符入符号栈，如果当前操作符
                 *    的优先级大于栈中的操作符，就直接入符号栈
                 *
                 *    如果有括号 先将左括号入栈 碰到右括号的时候，将符号栈中栈顶元素出栈，数字栈中两次出栈顶元素，进行运算，
                 *    将运算的结果插入数字栈中，直到为右括号便停止该循坏 并移除符号栈中的左括号
                 */
                if(ch=='('){
                    operStack.push(ch);
                }
                else if(ch==')'){
                    //获取符号并进行运算 进行消括号操作
                    while (operStack.peek()!='(') {
                        oper=operStack.pop();
                        num1 = numStack.pop();
                        num2 = numStack.pop();
                        res = numStack.cal(num1, num2, oper);
                        //把运算结果入数栈
                        numStack.push(res);
                    }
                    operStack.pop();//去掉左括号
                }
            else if (!operStack.isEmpty()) {
                //判断当前符号栈是否为空
                if (operStack.priority(ch) <= operStack.priority(operStack.peek())) {
                    num1 = numStack.pop();
                    num2 = numStack.pop();
                    oper = operStack.pop();
                    res = numStack.cal(num1, num2, oper);
                    //把运算结果入数栈
                    numStack.push(res);
                    //然后将当前的操作符入符号栈
                    operStack.push(ch);
                }
            else {
                    //如果当前的操作符的优先级大于栈中的操作符，就直接入符号栈
                    operStack.push(ch);
                }
            }else {
                //如果为空则直接入符号栈
                operStack.push(ch);
            }
        }
        else {//如果是数，则直接入数栈
                keepNum+=ch;
                //如果ch已经是最后一位，则直接入栈
                if(index==expression.length()-1){
                    numStack.push(Integer.parseInt(keepNum));
                }else {
                    //判断下一位是不是数字，如果是数字，就继续扫描，如果是运算符则入栈
                    //注意看后一位，不是index++
                    if(operStack.isOper(expression.substring(index+1,index+2).charAt(0))){
                      //如果后一位是运算符，则入栈keepNum="1" "123"
                      numStack.push(Integer.parseInt(keepNum));
                      // keepNum清空
                        keepNum="";
                    }
                }
            }
            //让index+1,并判断是否扫描到expression最后
            index++;
    }
    //当表达式扫描完毕，就顺序的从数栈和符号栈中pop出相应的数和符号，并运行
        while (!operStack.isEmpty()){
            num1=numStack.pop();
            num2=numStack.pop();
            oper=operStack.pop();
            res=numStack.cal(num1,num2,oper);
            numStack.push(res);
        }
        //将数栈的最后数，pop出，就是结果
        int res2=numStack.pop();
        System.out.printf("表达式%s = %d",expression,res2);
    }
    public static void main(String[] args) {
        String expression="(2-4)+3*6";
        compute(expression);
    }
}


中缀表达式转后缀表达式
大家可能会想：既然中缀表达式可以计算结果，我们为什么还要学习后缀表达呢？ 而且后缀表达式看起来不容易理解：

后缀表达式是计算机通常用的方法，因为它不用考虑优先级，可以直接进行出栈运算即可。

所以我们先学习一下如何使中缀表达式转化为后缀表式。

需要了解其法则：

中缀转后缀表达式

1.初始化两个栈，运算栈S1和存储中键结果的栈s2
2.从左至右扫描中缀表达式
3.遇到操作数时，将其压s2
4.遇到运算符时，比较其与s1栈顶运算符的优先级
4.1） 如果s1为空，或栈顶运算符为左括号，则直接将此运算符入栈
4.2)否则，如果优先级比栈顶运算符的高，也将运算符压入s1.
4.3)否则，将s1栈顶的运算符弹出并压入到s2中，再次转到4.1与s1中新的栈顶运算符相比较
5.遇到括号时：
5.1）如果是左括号，则直接入栈
5.2）如果是右括号，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃
6)重复步骤2-5 直到表达式的最右边
7）将s1剩余的运算符依次弹出并压入s2
8）依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式



我们来模拟一下其转化过程：

eg:(3+4)*5-2


需要注意的是，这里进行模拟的时候，采用的是两个栈，但是s2只有插入没有输出的过程，到最后运算完后，还需要将s2栈逆序输出，反而增加了复杂度，因此我们s2可以采用队列，list集合等方便输出。

代码：

首先将中缀表达式转为List集合，方便取元素：
//方法：将中缀表达式转成对应的List
    public static List<String> toInfixExpressionList(String s){
        //定义一个List，存放中缀表达式 对应的内容
        List<String> ls=new ArrayList<>();
        int i=0;
        String str;//对多位数进行处理
        char c=' ';
        do {
            //如果c是一个非数字，需要加入ls
            if((c=s.charAt(i))<'0'||(c=s.charAt(i))>'9'){
                ls.add(""+c);
                i++;
            }
            else {
                //如果是数字则需要考虑多位数
                str = "";//先将str置为“”
                while (i<s.length()&&(c=s.charAt(i))>='0'&&(c=s.charAt(i))<='9'){
                    str+=c;//拼接
                    i++;
                }
                ls.add(str);
            }
        }while (i<s.length());
        return ls;
    }

其次将表达式转为后缀表达式：
public  static List<String> reverse(List<String> ls){
      //定义两个栈
        Stack<String> s1=new Stack<>();//符号栈
      //说明：因为s2这个栈，在整个转换过程中，没有pop操作，而且后面还需要逆序输出
        //比较麻烦，则我们此处使用List<String> s2;
        List<String> s2=new ArrayList<>();//储存中间结果的List2
        //遍历ls
        for(String item:ls){
            //如果是数字，则直接放入s2
            if(item.matches("\\d+")){
                s2.add(item);
            }
            //左括号直接入栈
            else if(item.equals("(")){
                s1.push(item);
            }//如果是右括号，则依次弹出s1栈顶的运算符，并压入s2,直到遇到左括号为止
            else  if(item.equals(")")){
             while (!s1.peek().equals("(")){
                 s2.add(s1.pop());
             }
             s1.pop();//将（弹出s1栈，消除小括号
            }else {
                //当item的优先级小于或者等于s1栈顶优先级，先将s1栈顶的运算符弹出并加入到s2中，再次转到4.1与s1中新的
                //栈顶运算符相比较
                while (s1.size()!=0&&operation.getValue(s1.peek())>=operation.getValue(item)){
                    s2.add(s1.pop());
                }
                //还需要将item入栈
                s1.push(item);
            }
        }
        while (s1.size()!=0){
            s2.add(s1.pop());
        }
        return s2;//注意因为存放到List中，因此按顺序暑促的就是对应的后缀表达式对应的List
    }

此处s1栈，涉及到优先级的比较：
//编写一个类 可以返回运算符对那个的优先级
class operation{
    private static int add=1;
    private static int sub=1;
    private static int mul=2;
    private static int div=2;
    //写方法 返回其对应的优先级数字
    public static  int getValue(String operation){
        int res=0;
        switch (operation){
            case "+":res=add;break;
            case "-":res=sub;break;
            case "*":res=mul;break;
            case "/":res=div;break;
            default:
                break;
        }
        return res;
    }
}


便可以完成中缀转后缀。
后缀表达式求值（逆波兰表达式求值）
后缀表达式求值比较简单，不需要进行优先级判断，直接出栈计算即可。

从左至右扫描表达式，遇到数字时，将数字压入堆栈


遇到运算符号时，弹出栈顶的两个数，用运算符对他们做相应的计算（次顶元素和栈顶元素），并将结果入栈；
重复上述过程直至表达式最右边，最后运算得出的值即为表达式的结果

eg:(3+4)*5-2  其对应的后缀表达式：3 4 + 5 * 2 -





代码：
 //完成对逆波兰表达式的计算
    public static int compute(List<String> list){
        Stack<String> stack=new Stack<>();
        for(String item:list){
            //使用正则表达式来取数
            if(item.matches("\\d+")){
                stack.push(item);
            }
            else {
                //pop出两个数 并进行运算  再将结果入栈
                int num1=Integer.valueOf(stack.pop());
                int num2=Integer.valueOf(stack.pop());
               int res=0;
                if(item.equals("+")){
                    res=num1+num2;
                }
                else if(item.equals("-")){
                    res=num2-num1;
                }
                else if(item.equals("*")){
                    res=num1*num2;
                }
                else if(item.equals("/")){
                    res=num2/num1;
                }else {
                    throw new RuntimeException("运算符号有误");
                }
                stack.push(String.valueOf(res));
            }
        }
        return Integer.valueOf(stack.pop());
    }
  //将一个逆波兰表达式，依次将数据和运算符放入到Arraylist中
    public static List<String> getListString(String suffixExpression){
       //将sufferExpression分割
       String[] split=suffixExpression.split(" ");
      List<String> list=new ArrayList<>();
      for(String str:split){
          list.add(str);
      }
      return list;
    }

前缀表达式（波兰表达式）
前缀表达式与后缀表达式正好相反，懂了后缀表达式，便可以轻松写出前缀表达式

需要注意：前缀表达式 符号在前，数字在后，我们进行运算时，需要从右至左进行运算，其余步骤一样。

例如，- 1 + 2 3，它等价于1-(2+3)。大家举一反三，便可以自己求出，本文不再赘述。

有什么问题欢迎大家前来提问。

中缀表达式求值问题
中缀表达式的求值问题是一个比较常见的问题之一，我们通常在编写程序时，直接写出表达式让编译器去处理，很少去关心编译器是怎么对表达式进行求值的，今天我们来一起了解一下其中具体的原理和过程。
表达式一般来说有三种：前缀表达式、中缀表达式、后缀表达式，其中后缀表达式又叫做逆波兰表达式。中缀表达式是最符合人们思维方式的一种表达式，顾名思义，就是操作符在操作数的中间。而前缀表达式和后缀表达式中操作符分别在操作数的前面和操作数的后面。举个例子：
3+2
这个是最简单的一个中缀表达式。而其等同的前缀表达式形式为+32，后缀表达式形式为32+。
那么一些朋友可能会问既然中缀表达式最符合人类的思维习惯，为什么还需要前缀表达式和后缀表达式？先看一个例子，假如在前面的表达式基础上加一点东西：
3+2*5
此时的表达式很显然，如果进行计算，则先计算2*5，最后计算加法。但是如果需要先计算加法运算呢？则必须加上括号，(3+2)*5。
而如果用后缀表达式来表示，则为 32+5*，那么该表达式的计算顺序为3+2 —> (3+2)*5。
区别就在这里，后缀表达式不需要用括号就能表示出 整个表达式哪部分运算先进行。同理，前缀表达式也是如此。这种表达式正好最符合计算机的处理方式，因为后缀表达式和前缀表达式求值不需要考虑优先级的问题，计算机处理起来便简单很多。
今天我们这里主要讲解中缀表达式和后缀表达式(前缀表达式和后缀表达式很类似，就不做过多赘述)，下面是讲解大纲：
中缀表达式如何直接求值？
后缀表达式如何直接求值？
中缀表达式如何转换为后缀表达式？
1.中缀表达式直接求值
对于中缀表达式求值来说，一般最常见的直接解决办法就是利用栈，一个栈用来保存操作数，一个栈用来保存操作符。
为了简便起见，暂时表达式中只考虑简单的+，-，*，/运算，只有圆括号，并且都是整数。
假如有这样一个表达式：((3+5*2)+3)/5+6/4*2+3
对于这样一个表达式，如果让你来设计操作数和操作符进栈的出栈的规则，你会怎么设计？
先不看这么复杂的表达式，考虑一下简单点的，还是前面的3+2*5，那么很显然先进行乘法运算，后进行加法运算，但是由于操作符在操作数中间，所以当一个操作符进操作符栈时，该操作符的两个操作数并没有都进入到操作数栈中，那么如何解决呢？只有在后面一个操作符进操作符栈时，前面的一个操作符所作用的两个操作数才会全部进栈。比如3+2*5,栈的变化过程为：
操作数栈：3      操作数栈：3   操作数栈：3 2
操作符栈：空     操作符栈：+  操作符栈：+
注意此时遇到操作符“*”，是不是需要弹出操作数栈中的两个操作数进行运算呢，很显然不是，因为乘法运算法比操作符栈的栈顶运算符优先级高，也就是说当前的操作符在“+”前进行运算，那么还需要将当前操作符压栈，则变成：
操作数栈：3 2   操作数栈：3 2 5
操作符栈：+ *  操作符栈：+ *
此时到了表达式的结尾，既然栈顶的操作符的优先级比栈底的操作符的优先级高，那么可以取操作符栈的栈顶操作符和操作数栈的栈顶两个元素进行计算，则得到2*5=10，(注意从操作数栈先弹出的操作数为右操作数)。此时得到10 ，则应该把10继续压到操作数栈中，继续取操作符栈的栈顶操作符，依次进行下去，则当操作符栈为空时表示计算过程完毕，此时操作数栈中剩下的唯一元素便是整个表达式的值。
再换个例子：2*5+3,这个表达式跟前面表达式的结果虽然相同，但是操作数和操作符入栈和出栈的顺序发生了很大变化：
操作数栈：2     操作数栈：2   操作数栈：2 5
操作符栈：空    操作符栈：*   操作符栈：*
此时遇到“+”，而操作符栈的栈顶操作符为“*”，栈顶操作符优先级更高，表示此时可以取操作符栈顶操作符进行运算，那么栈变成：
操作数栈：10   操作数栈：10 3
操作符栈：空    操作符栈：+
后面的过程跟前面一个例子类似。
如果复杂一点，比如包含有括号，连续的乘除法这些怎么处理呢？道理是一样的，对于左括号直接入栈，碰到右括号，则一直将操作符退栈，直到碰到左括号，则括号中的表达式计算完毕。对于连续的乘除法，跟前面例子中处理过程类似。只需要记住一点：只有当前操作符的优先级高于操作符栈栈顶的操作符的优先级，才入栈，否则弹出操作符以及操作数进行计算直至栈顶操作符的优先级低于当前操作符，然后将当前操作符压栈。当所有的操作符处理完毕(即操作符栈为空时)，操作数栈中剩下的唯一一个元素便是最终的表达式的值。而操作符的优先级为：+和-优先级是一样的，*和/优先级是一样的，+、-的优先级低于*、/的优先级。
不过需要注意的是在求值之前需要对表达式进行预处理，去掉空格、识别 负号(区分“-”是作为减号还是负号)，提取操作数等。
对于“-”的区分，主要判别方法为：
1)若前一个字符为‘('，则必定为负号；
2)若前一个字符为')'或者数字，则必定为减号；
3)若前面一个字符为其他运算符，如*，/，则必定是负号；
3)若前面没有字符，即该字符为表达式的第一个字符，则必定是负号。
也就是说只有一种情况下，”-“是作为减号使用的，就是前一个字符为')'或者数字的时候。
如果判断出“-”是作为负号使用的，这里我采用“#”来代替“-”，并将其作为一种运算(优先级最高)。比如：-3*2
我采取的做法是将"#"入栈，然后当遇到“*”时，由于栈顶操作符为"#"，因此取#，然后取操作数栈的栈顶元素(只取一个)进行运算，然后再把结果压栈。
下面是具体实现：
/*2014.5.6 测试环境: mingw*/
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
vector preParse(char *str)   //对中缀表达式进行预处理，分离出每个token
{
vector tokens;
int len = strlen(str);
char *p = (char *)malloc((len+1)*sizeof(char));  //注意不要用 char *p = (char *)malloc(sizeof(str))来申请空间
int i=0,j=0;
while(i
{
if(str[i]==' ')
{
i++;
continue;
}
p[j++] = str[i++];
}
p[j]='\0';
j=0;
len = strlen(p);
while(j
{
char temp[2];
string token;
switch(p[j])
{
case '+':
case '*':
case '/':
case '(':
case ')':
{
temp[0] =p[j];
temp[1] = '\0';
token=temp;
tokens.push_back(token);
break;
}
case '-':
{
if(p[j-1]==')'||isdigit(p[j-1]))  //作为减号使用
{
temp[0] =p[j];
temp[1] = '\0';
token=temp;
tokens.push_back(token);
}
else    //作为负号使用
{
temp[0] ='#';
temp[1] = '\0';
token=temp;
tokens.push_back(token);
}
break;
}
default:     //是数字
{
i = j;
while(isdigit(p[i])&&i
{
i++;
}
char *opd = (char *)malloc(i-j+1);
strncpy(opd,p+j,i-j);
opd[i-j]='\0';
token=opd;
tokens.push_back(token);
j=i-1;
free(opd);
break;
}
}
j++;
}
free(p);
return tokens;
}
int getPriority(string opt)
{
int priority;
if(opt=="#")
priority = 3;
else if(opt=="*"||opt=="/")
priority = 2;
else if(opt=="+"||opt=="-")
priority = 1;
else if(opt=="(")
priority = 0;
return priority;
}
void calculate(stack &opdStack,string opt)
{
if(opt=="#")  //进行负号运算
{
int opd = opdStack.top();
int result = 0-opd;
opdStack.pop();
opdStack.push(result);
cout<
}
else if(opt=="+")
{
int rOpd = opdStack.top();
opdStack.pop();
int lOpd = opdStack.top();
opdStack.pop();
int result = lOpd + rOpd;
opdStack.push(result);
cout<
}
else if(opt=="-")
{
int rOpd = opdStack.top();
opdStack.pop();
int lOpd = opdStack.top();
opdStack.pop();
int result = lOpd - rOpd;
opdStack.push(result);
cout<
}
else if(opt=="*")
{
int rOpd = opdStack.top();
opdStack.pop();
int lOpd = opdStack.top();
opdStack.pop();
int result = lOpd * rOpd;
opdStack.push(result);
cout<
}
else if(opt=="/")
{
int rOpd = opdStack.top();
opdStack.pop();
int lOpd = opdStack.top();
opdStack.pop();
int result = lOpd / rOpd;
opdStack.push(result);
cout<
}
}
int evaMidExpression(char *str)   //中缀表达式直接求值
{
vector tokens = preParse(str);
int i=0;
int size = tokens.size();
stack opdStack;     //存储操作数
stack optStack;   //存储操作符
for(i=0;i
{
string token = tokens[i];
if(token=="#"||token=="+"||token=="-"||token=="*"||token=="/")
{
if(optStack.size()==0)   //如果操作符栈为空
{
optStack.push(token);
}
else
{
int tokenPriority = getPriority(token);
string topOpt = optStack.top();
int topOptPriority = getPriority(topOpt);
if(tokenPriority>topOptPriority)
{
optStack.push(token);
}
else
{
while(tokenPriority<=topOptPriority)
{
optStack.pop();
calculate(opdStack,topOpt);
if(optStack.size()>0)
{
topOpt = optStack.top();
topOptPriority = getPriority(topOpt);
}
else
break;
}
optStack.push(token);
}
}
}
else if(token=="(")
{
optStack.push(token);
}
else if(token==")")
{
while(optStack.top()!="(")
{
string topOpt = optStack.top();
calculate(opdStack,topOpt);
optStack.pop();
}
optStack.pop();
}
else   //如果是操作数，直接入操作数栈
{
opdStack.push(atoi(token.c_str()));
}
}
while(optStack.size()!=0)
{
string topOpt = optStack.top();
calculate(opdStack,topOpt);
optStack.pop();
}
return opdStack.top();
}
int main(int argc, char *argv[])
{
char *str = "((3+5*2)+3)/5+(-6)/4*2+3";
cout<
return 0;
}
运行结果：
2.后缀表达式直接求值
由于后缀表达式不需要用括号来表示计算顺序，因此处理起来比较简单，具体的可以参照：
3.中缀表达式如何转为后缀
大部分数据结构教材在讲述 栈的时候都会涉及到中缀表达式转为后缀表达式的问题，因为这个是栈的典型应用之一。因此很多教材上都会利用栈来进行转换，这里我们来讨论一下最常见的两种转换思路和一种简便的验证方法。
利用二叉树进行转换
由于二叉树本身结构的特殊性，使得我们可以利用它来很轻松地将中缀表达式转变成后缀表达式，事实上，只要根据中缀表达式建立好相应的二叉树之后，直接对二叉树进行前序遍历和后序遍历便可得到前缀表达式和后缀表达式。在利用二叉树来表示表达式时，用叶子节点来存储操作数，用内部节点存储操作符，比如这样一个表达式3*5+5/2+(3+5)*2，表示成二叉树的形式(注意其有等同的其他形式)就是：
其实讲中缀表达式的过程转变成二叉树的形式是一个递归的过程，比如有一个表达式，其对应的的二叉树的根节点必定是优先级最低的操作符(也就是说是整个表达式中最后进行的运算操作)，然后再在操作符的左部分中找出最后进行的操作符作为根节点的左孩子，在操作符的右部分中找出最后进行的操作符作为根节点的右孩子，然后知道左部分或者右部分是单纯的操作数，则作为叶子节点，直到整个二叉树建立完毕。
下面是具体实现：
参考了一下这篇博文的实现，但是这篇博文没有考虑减号作为负号使用的情况。
/*
测试环境：VS2010
*/
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef struct node
{
struct node *left;
struct node *right;
char *data;
}BinTree;
char * preProcess(char *str)   //预处理，除去空格，将负号替代为#
{
int len = strlen(str);
char *p = (char *)malloc(sizeof(char)*len);
int i=0,j=0;
while(i
{
if(str[i]==' ')
{
i++;
continue;
}
p[j++] = str[i++];
}
p[j]='\0';
j=0;
len = strlen(p);
while(j
{
if(p[j]=='-')
{
if(!(p[j-1]==')'||isdigit(p[j-1])))  //作为减号使用
{
p[j]='#';
}
}
j++;
}
return p;
}
/*
最后执行的操作符一定是在括号外面，也就是说brackets一定是等于0的，
*/
int indexOfOpt(char *str,int begin ,int end)   //寻找最后执行的操作符的下标
{
int i;
int brackets=0;                    //所在括号层次
int index = -1;
int existAddOrMinus = 0;
int existMulOrDevide = 0;
while(str[begin]=='('&&str[end]==')')   //去除最外层的括号
{
begin++;
end--;
}
for(i=begin;i<=end;i++)
{
if(str[i]=='(')
brackets++;
else if(str[i]==')')
brackets--;
else if((str[i]=='+'||str[i]=='-')&&brackets==0)
{
index = i;
existAddOrMinus = 1;    //存在加减号
}
else if((str[i]=='*'||str[i]=='/')&&brackets==0&&existAddOrMinus==0)
{
index = i;
existMulOrDevide = 1;  //存在乘除号
}
else if(str[i]=='#'&&brackets==0&&existAddOrMinus==0&&existMulOrDevide==0)  //用'#'代表负号
{
index = i;
}
}
return index;
}
BinTree * createBinTree(char *str,int begin,int end)
{
BinTree *p =(BinTree *)malloc(sizeof(BinTree));;
int index = indexOfOpt(str,begin,end);
cout<
if(index==-1)   //表示只有操作数了
{
while(str[begin]=='('&&str[end]==')')
{
begin++;
end--;
}
p->data = (char *)malloc(sizeof(end-begin+2));
int i,j=0;
for(i=begin;i<=end;i++)
p->data[j++] = str[i];
p->data[j]='\0';
p->left = NULL;
p->right = NULL;
cout<data<
}
else
{
p->data = (char*)malloc(2);
p->data[0] = str[index];
p->data[1]='\0';
cout<data<
while(str[begin]=='('&&str[end]==')')
{
begin++;
end--;
}
if(str[index]=='#')  //是负号
{
p->left = NULL;
}
else
{
p->left = createBinTree(str,begin,index-1);
}
p->right = createBinTree(str,index+1,end);
}
return p;
}
void preOrder(BinTree *root)
{
if(root!=NULL)
{
cout<data<
preOrder(root->left);
preOrder(root->right);
}
}
void inOrder(BinTree *root)
{
if(root!=NULL)
{
inOrder(root->left);
cout<data<
inOrder(root->right);
}
}
void postOrder(BinTree *root)
{
if(root!=NULL)
{
postOrder(root->left);
postOrder(root->right);
cout<data<
}
}
int main(void)
{
char *str = "((3+5*2)+3)/5+(-6)/4*2+3";
char *newStr = preProcess(str);
cout<
BinTree *root=createBinTree(newStr,0,strlen(newStr)-1);
inOrder(root);
cout<
postOrder(root);
cout<
system("pause");
return 0;
}
上述代码在VS2010下运行是没有问题的，但是在gcc下编译运行会崩溃，调试了很久没发现原因(如果有哪位朋友知道原因的请麻烦告知)。测试结果：
利用栈进行转换
利用栈进行转换的思路其实跟前面直接对中缀表达式求值的过程类似，在这过程中需要一个栈用来保存操作符optStack，需要一个数组用来保存后缀表达式suffix[]，然后从头到尾扫描表达式
1)如果遇到操作符，则跟optStack的栈顶操作符比较优先级，如果大于栈顶操作符的优先级，则入栈，否则不断取栈顶操作符加到suffix的末尾，直到栈顶操作符优先级低于该操作符，然后将该操作符入栈；
2)遇到操作数，直接加到suffix的末尾
3)遇到左括号，入栈；
4)遇到右括号，则依次弹出栈顶操作符加到suffix的末尾，直到遇到左括号，然后将左括号出栈。
具体实现：
/*2014.5.6 测试环境: mingw*/
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
vector preParse(char *str)   //对中缀表达式进行预处理，分离出每个token
{
vector tokens;
int len = strlen(str);
char *p = (char *)malloc((len+1)*sizeof(char));  //注意不要用 char *p = (char *)malloc(sizeof(str))来申请空间
int i=0,j=0;
while(i
{
if(str[i]==' ')
{
i++;
continue;
}
p[j++] = str[i++];
}
p[j]='\0';
j=0;
len = strlen(p);
while(j
{
char temp[2];
string token;
switch(p[j])
{
case '+':
case '*':
case '/':
case '(':
case ')':
{
temp[0] =p[j];
temp[1] = '\0';
token=temp;
tokens.push_back(token);
break;
}
case '-':
{
if(p[j-1]==')'||isdigit(p[j-1]))  //作为减号使用
{
temp[0] =p[j];
temp[1] = '\0';
token=temp;
tokens.push_back(token);
}
else    //作为负号使用
{
temp[0] ='#';
temp[1] = '\0';
token=temp;
tokens.push_back(token);
}
break;
}
default:     //是数字
{
i = j;
while(isdigit(p[i])&&i
{
i++;
}
char *opd = (char *)malloc(i-j+1);
strncpy(opd,p+j,i-j);
opd[i-j]='\0';
token=opd;
tokens.push_back(token);
j=i-1;
free(opd);
break;
}
}
j++;
}
free(p);
return tokens;
}
int getPriority(string opt)
{
int priority;
if(opt=="#")
priority = 3;
else if(opt=="*"||opt=="/")
priority = 2;
else if(opt=="+"||opt=="-")
priority = 1;
else if(opt=="(")
priority = 0;
return priority;
}
vector toSuffix(char *str)  //转变为后缀形式
{
vector tokens = preParse(str);
int i=0;
int size = tokens.size();
vector suffix;     //存储后缀表达式
stack optStack;   //存储操作符
for(i=0;i
{
string token = tokens[i];
if(token=="#"||token=="+"||token=="-"||token=="*"||token=="/")
{
if(optStack.size()==0)   //如果操作符栈为空
{
optStack.push(token);
}
else
{
int tokenPriority = getPriority(token);
string topOpt = optStack.top();
int topOptPriority = getPriority(topOpt);
if(tokenPriority>topOptPriority)
{
optStack.push(token);
}
else
{
while(tokenPriority<=topOptPriority)
{
optStack.pop();
suffix.push_back(topOpt);
if(optStack.size()>0)
{
topOpt = optStack.top();
topOptPriority = getPriority(topOpt);
}
else
break;
}
optStack.push(token);
}
}
}
else if(token=="(")
{
optStack.push(token);
}
else if(token==")")
{
while(optStack.top()!="(")
{
string topOpt = optStack.top();
suffix.push_back(topOpt);
optStack.pop();
}
optStack.pop();
}
else   //如果是操作数，直接入操作数栈
{
suffix.push_back(token);
}
}
while(optStack.size()!=0)
{
string topOpt = optStack.top();
suffix.push_back(topOpt);
optStack.pop();
}
return suffix;
}
int main(int argc, char *argv[])
{
char *str = "((3+5*2)+3)/5+(-6)/4*2+3";
vector suffix = toSuffix(str);
int size = suffix.size();
for(int i=0;i
cout<
cout<
return 0;
}
测试结果：
简便验证办法
最后一种办法可以很快速地求出中缀表达式对应的前缀表达式和后缀表达式，就是添括号去括号法。
比如有表达式： (3+5*2)-2*3
先对每一个小部分添加括号： ((3+(5*2))-(2*3))
然后将每个操作符放到括号后面：((3(52)*)+(23)*)-
然后去括号：352*+23*-
便得到了后缀表达式，前缀表达式类似(只需把操作符放到括号前面即可)。

利用栈中缀表达式求值
头文件
#include<stdlib.h>
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MAXSIZE 100
typedef struct
{
	SElemType *base;
	SElemType *top;
	int stacksize;
}Sqstack;
Status Initstack(Sqstack &S)
{
    S.base=new SElemType[MAXSIZE];
	if(!S.base) exit(OVERFLOW);
	S.top=S.base;
	S.stacksize=MAXSIZE;
	return OK;
}
Status emptystack(Sqstack S)
{
  if(S.top==S.base)
	  return 1;
  else return 0;
}
Status push(Sqstack &S,SElemType e)
{
if(S.top-S.base==S.stacksize)  return ERROR;
*S.top++=e;
return OK;
}
Status Pop(Sqstack &S,SElemType &e)
{
if(S.top==S.base)
 return ERROR;
e=*--S.top;
return OK;
}
Status GetTop(Sqstack S)//),SElemType &e)
{
if(S.top!=S.base)
return *(S.top-1);
}
const char oper[7] = { '+', '-', '*', '/', '(', ')', '#' };
bool In(char ch) {//判断ch是否为运算符
	int i;
	for ( i = 0; i < 7; i++) {
		if (ch == oper[i]) {
			return true;
		}
	}
	return false;
}
char Precede(char theta1, char theta2) {//判断运算符优先级
	if ((theta1 == '(' && theta2 == ')') || (theta1 == '#' && theta2 == '#')) {
		return '=';
	} else if (theta1 == '(' || theta1 == '#' || theta2 == '(' || (theta1
			== '+' || theta1 == '-') && (theta2 == '*' || theta2 == '/')) {
		return '<';
	} else
		return '>';
}
char Operate(char first, char theta, char second) {//计算两数运算结果
	switch (theta) {
	case '+':
		return (first - '0') + (second - '0') + 48;
	case '-':
		return (first - '0') - (second - '0') + 48;
	case '*':
		return (first - '0') * (second - '0') + 48;
	case '/':
		return (first - '0') / (second - '0') + 48;
	}
	return 0;
}


主函数
#include<stdio.h>
typedef int Status;
typedef char SElemType;
#include"Sqstack.h"
char EvaluateExpression()
{
    Sqstack OPND;
Sqstack OPTR;
	Initstack(OPND);
	Initstack(OPTR);
	char ch,theta,a,b,x;
	push(OPTR, '#');
	printf("请输入要求的表达式");
	ch=getchar();
	while (ch!='#'||GetTop(OPTR)!='#')
	{
		if (!In(ch)) { push(OPND,ch); ch=getchar(); }
		else
			switch (Precede(GetTop(OPTR),ch))
			{
			case '<':
				push(OPTR, ch); ch=getchar();
				break;
			case '>':
				Pop(OPTR,theta);
				Pop(OPND, b); Pop(OPND,a);
				push(OPND,Operate(a,theta,b));
				break;
			case '=':
				Pop(OPTR, x); ch=getchar();
				break;
			}
	}
	return GetTop(OPND);
}
int main(){
    char a;
a=EvaluateExpression();
printf("%c",a);
return 0;
}



注：此程序只能计算0~ 9的数因为在ASCII表中只能转换0~ 9的数为此程序的弊端；

中缀表达式到后缀表达式的转换
例：(6/3+5)6

1.遇到操作数，直接输出；

2.栈为空时，遇到运算符，入栈；

3.遇到左括号，将其入栈；

4.遇到右括号，执行出栈操作，并将出栈的元素输出，直到弹出栈的是左括号，左括号不输出；

5.遇到其他运算符’+”-””/’时，弹出所有优先级大于或等于该运算符的栈顶元素，然后将该运算符入栈；

6.最终将栈中的元素依次出栈，输出。

首先从左向右扫描遇到左括号它比#的优先级高将它入栈

然后遇到操作数6输出   6

遇到/号遇到左括号入栈  6

遇到操作数输出3       63

遇到+号由于/号优先级大于+号所以弹出/号并将+号压入栈         63/

遇到操作数5输出       63/5

遇到右括号与左括号抵消掉并将+号弹出    63/5+

遇到乘号比#的优先级高入栈    63/5+

与操作数6输出       63/5+6

最后将乘号弹出    63/5+6*