Showing posts with label stacks. Show all posts
Showing posts with label stacks. Show all posts
FIx Left Parentheses Program using Stacks
Write a program to fix the left parentheses for the given expression properly to form a balanced expression.
---------------------------Program----------------------------------
import java.util.*;
import java.lang.*;
class FixLeftParentheses {
String input="";
FixLeftParentheses(String x){
this.input=x;
}
public String balanceParentheses(){
if(input.length()==0){
return "";
}
if(input.charAt(0)==')'){
return "()";
}
if (input.length()==1) {
return input;
}
if(input.length()<=2){
if(input.charAt(1)==')'){
String output="("+input.charAt(0)+")";
return output;
}
}
Stack<Character> operators = new Stack<Character>();
Stack<String> operands = new Stack<String>();
for (int i = 0; i < input.length(); i++){
switch (input.charAt(i)){
case '+':
case '-': // Operator case
case '*':
case '/':
operators.push(input.charAt(i));
break;
case '0':
case '1':
case '2':
case '3':
case '4': // "operand" case
case '5':
case '6':
case '7':
case '8':
case '9':
String s = "";
s += input.charAt(i);
operands.push(s);
break;
case ')':
// closing paren case
String a,b;
char c;
if(operands.isEmpty()){
throw new ArrayIndexOutOfBoundsException("Expression not clear");
}else{
a = operands.pop();
}
if(operands.isEmpty()){
throw new ArrayIndexOutOfBoundsException("Expression not clear");
}else{
b = operands.pop();
}
if(operators.isEmpty()){
throw new ArrayIndexOutOfBoundsException("Expression not clear");
}else{
c = operators.pop();
}
StringBuilder buf = new StringBuilder();
buf.append("(");
buf.append(b);
buf.append(c);
buf.append(a);
buf.append(")");
operands.push(buf.toString());
break;
case ' ':
break;
}
}
return operands.pop();
}
public static void main(String[] args){
FixLeftParentheses obj = new FixLeftParentheses("2+3)*5+6)*7+8))");
String output=obj.balanceParentheses();
System.out.println(output);
}
}
}
Infix to PostFix Conversion using Stacks
Write a program to convert infix notation to postfix notation using stack.
----------------------------Program-------------------------------------
public class InfixToPostfix {
private Stack theStack;
private String infix;
private String output = "";
public InfixToPostfix(String infix) {
this.infix= infix;
int stackSize = infix.length();
theStack = new Stack(stackSize);
}
public String convertToPostfix() {
for (int j = 0; j < infix.length(); j++) {
char ch = infix.charAt(j);
switch (ch) {
case '+':
case '-':
gotOperator(ch, 1);
break;
case '*':
case '/':
gotOperator(ch, 2);
break;
case '(':
theStack.push(ch);
break;
case ')':
gotParenthesis(ch);
break;
default:
output = output + ch;
break;
}
}
while (!theStack.isEmpty()) {
output = output + theStack.pop();
}
return output;
}
public void gotOperator(char opThis, int prec1) {
while (!theStack.isEmpty()) {
char opTop = theStack.pop();
if (opTop == '(') {
theStack.push(opTop);
break;
}
else {
int prec2;
if (opTop == '+' || opTop == '-')
prec2 = 1;
else
prec2 = 2;
if (prec2 < prec1) {
theStack.push(opTop);
break;
}
else
output = output + opTop;
}
}
theStack.push(opThis);
}
public void gotParenthesis(char ch){
while (!theStack.isEmpty()) {
char chx = theStack.pop();
if (chx == '(')
break;
else
output = output + chx;
}
}
class Stack {
private int maxSize;
private char[] stackArray;
private int top;
public Stack(int max) {
maxSize = max;
stackArray = new char[maxSize];
top = -1;
}
public void push(char j) {
stackArray[++top] = j;
}
public char pop() {
return stackArray[top--];
}
public char peek() {
return stackArray[top];
}
public boolean isEmpty() {
return (top == -1);
}
}
}
Parentheses Balancing Program using Stacks
Write a program to determine whether the parentheses are properly balanced using stacks
-----------------------------Program------------------------------------
Postfix Expression Evaluation Program
Write a program to evaluate a postfix expression using stack
-------------------------Program---------------------------------------
import java.util.Stack;
public class PostfixEvaluation {
private static String postfixExpr;
public PostfixEvaluation(String postfix) {
this.postfixExpr= postfix;
}
/**
* Evaluate postfix expression
*
* @param postfix The postfix expression
*/
public Double evaluate() {
Stack s = new Stack();
Double result = 0.0;
String operand = "";
for(int i = 0; i<postfixExpr.length();i++){
if(Character.isDigit(postfixExpr.charAt(i)) == true || ( postfixExpr.charAt(i)=='-' ) ){
if( postfixExpr.charAt(i)=='-' && i!=postfixExpr.length()-2 && i!=postfixExpr.length()-1)
{
if( Character.isDigit(postfixExpr.charAt(i+1)) && Character.isDigit(postfixExpr.charAt(i+1)) == true) {
operand="-";
i++;
}
}
if ( postfixExpr.charAt(i)!='-' )
{
operand = operand + postfixExpr.charAt(i);
if(Character.isDigit(postfixExpr.charAt(i+1)) == false){
s.push(operand);
operand = "";
}
}
}
if(postfixExpr.charAt(i) == '+'){
Double x = Double.parseDouble((String) s.pop()) + Double.parseDouble((String) s.pop());
result = x ;
s.push(String.valueOf(x));
}
if(postfixExpr.charAt(i) == '-'){
Double p =Double.parseDouble((String) s.pop());
Double q =Double.parseDouble((String) s.pop());
Double x = p-q;
result = x ;
s.push(String.valueOf(x));
}
if(postfixExpr.charAt(i) == '*'){
Double x = Double.parseDouble((String) s.pop()) * Double.parseDouble((String) s.pop());
result = x ;
s.push(String.valueOf(x));
}
if(postfixExpr.charAt(i) == '/'){
Double p =Double.parseDouble((String) s.pop());
Double q =Double.parseDouble((String) s.pop());
if(q!=0){
Double x = p/q;
result = x ;
s.push(String.valueOf(x));
}
else
{
throw new ArithmeticException("Division by zero error");
}
}
}
return result;
}
// public static void main(String[] args) {
// String postfix = "3 2 /";
//
// String output;
//
// PostfixEvaluation pfe = new PostfixEvaluation(postfix);
//
// Double value = pfe.evaluate();
// System.out.println(value);
//
// }
}
Advantages and Disadvantages of stacks and Queues
Stack/Queue are ideal for enforcing sequential rules of access (LIFO & FIFO as you stated) while Array is ideal for allowing random access as desired.
Subscribe to:
Posts
(
Atom
)