使用栈实现表达式求值 |
您所在的位置：网站首页 › 用栈求中缀表达式的值的算法 › 使用栈实现表达式求值 |
使用栈实现表达式求值
|
为了实现用栈计算算数表达式的值，需设置两个工作栈：用于存储运算符的栈opter，以及用于存储操作数及中间结果的栈opval。 算法基本思想如下： （1）首先将操作数栈opval设为空栈，而将'#'作为运算符栈opter的栈底元素，这样的目的是判断表达式是否求值完毕。 （2）依次读入表达式的每个字符，表达式须以'#'结尾，若是操作数则入栈opval，若是运算符,则将此运算符c与opter的栈顶元素top比较优先级后执行相应的操作，（具体操作如下：(i)若top的优先级小于c，即topc，则表明可以计算，此时弹出opval的栈顶两个元素，并且弹出opter栈顶的的运算符，计算后将结果放入占opval中。）直至opter的栈顶元素和当前读入的字符均为'#',此时求值结束。 算符间的优先关系如下表所示：
表中需要注意的是θ1为opter的栈顶元素，θ2位从表达式中读取的操作符，此优先级表可以用二维数组实现，具体见代码（表来源：严蔚敏《数据结构》）。 具体代码如下： #include //输入的表达式要以'#'结尾，如‘5+6*3/(3-1)#’ #include #include #include #include using namespace std; stack opter; //运算符栈 stack opval; //操作数栈 int getIndex(char theta) //获取theta所对应的索引 { int index = 0; switch (theta) { case '+': index = 0; break; case '-': index = 1; break; case '*': index = 2; break; case '/': index = 3; break; case '(': index = 4; break; case ')': index = 5; break; case '#': index = 6; default:break; } return index; } char getPriority(char theta1, char theta2) //获取theta1与theta2之间的优先级 { const char priority[][7] = //算符间的优先级关系 { { '>','>','','>','','>','>','>','','>' }, { '>','>','>','>','','>' }, { '','>' }, { ' |
【本文地址】